1. 선형 리스트(linear list)

"해당 글은 C를 기준으로 작성되었음."

1. 선형 리스트(Linear list):

---

ordered list which each node has unique successor.

• 4 Basic Operation: Insertion, Deletion, Retrieval, Traversal
• STRUCTURE

  • Head
  • Data node: dataPtr link to next node

---

1. Insertion(삽입): Retrieve를 통해 삽입위치를 찾은 후, case에 따라 새 노드를 삽입.

#case는 pPre의 NULL여부를 통해 판단한다.

case1. 처음 또는 맨 앞에 삽입 (pPre == NULL)

1. set new_node link to list head
2. set list head to new_node

case2. 중간 또는 맨 끝에 삽입 (pPre != NULL)

1. set new_node link to list head
2. set list head to new_node

2. Deletion(삭제): 해당 리스트에 target이 존재하는지 retrieve 후, 선행자의 link 포인터를 조정, 이후 target node 삭제

#search function을 통해 target의 위치(pLoc)와 선행자(pPre)를 받아 매개변수로 넘겨준다.

case1. 처음 또는 맨 앞 노드 삭제 (pPre == NULL)

1. set list head to pLoc link

case2. 그외의 경우 (pPre != NULL)

1. set pPre link to pLoc link

이후 pLoc이 가리키고 있는 node 삭제.

3. Search: Sequntial search

---

2. Complex Implementation

1. Circulary Linked lists: last node의 link가 first node를 가리키는 형태의 선형 리스트.

• Application! 백준 1158번: 요세푸스 문제

#include <stdio.h>
#include <stdlib.h> // malloc, free

//백준 1158번- 요세푸스 문제

typedef struct person {
	int num;
	int exist; //제거 여부
	struct person* link;

}PERSON;

typedef struct circle
{
	int cnt;
	PERSON* head;
	PERSON* rear;
}CIRCLE;

void printCircle(CIRCLE* circle)
{
	PERSON* pLoc = circle->head;

	do {
		printf("%d ", pLoc->num);
		pLoc = pLoc->link;

	} while (pLoc != circle->head);

	printf("\n");
}


CIRCLE* createCircle() {
	CIRCLE* C = malloc(sizeof(CIRCLE));
	C->cnt = 0;
	C->head = NULL;
	C->rear = NULL;

	return C;
}

PERSON* createPerson() {
	PERSON* p = malloc(sizeof(PERSON));
	p->link = NULL;

	return p;
}

int insert(CIRCLE* circle, int data) {
	PERSON* new_person = createPerson();
	if (!new_person) return 0;

	new_person->num = data;
	new_person->exist = 1;

	// 1. insert in empty 2. 그 이후 끝에 추가
	if (circle->cnt == 0)
	{
		circle->head = new_person;
		circle->rear = new_person;
		new_person->link = new_person;
	}
	else
	{
		circle->rear->link = new_person;
		new_person->link = circle->head;
		circle->rear = new_person;
	}
	circle->cnt += 1;

	//printCircle(circle);

	return 1;
}

void destroyCircle(CIRCLE* circle)
{
	PERSON* delLoc;

	while (1)
	{
		delLoc = circle->head;
		if (delLoc != circle->rear)
		{
			circle->head = circle->head->link;
			free(delLoc);
		}
		else {
			free(circle->rear);
			break;
		}
	}
	free(circle);
}

void printYosepus(CIRCLE* circle, int interval)
{
	PERSON* pLoc = circle->head;
	int count = 1;

	printf("<");
	while (circle->cnt != 0)
	{
		while (count < interval)
		{
			pLoc = pLoc->link;
			if (pLoc->exist) count++;
		}
		pLoc->exist = 0;

		if (circle->cnt == 1) printf("%d>", pLoc->num);
		else printf("%d, ", pLoc->num);

		circle->cnt -= 1;
		count = 0;
	}
}


int main() {
	int n, k;

	CIRCLE* circle = createCircle();

	scanf("%d %d", &n, &k);

	for (int i = 0; i < n; i++) {
		insert(circle, i + 1);
	}


	printYosepus(circle, k);

	destroyCircle(circle);

	return 0;
}

2. Doubly Linked lists: 역방향 link를 추가해, 쌍방향 순회가 모두 가능한 선형 리스트

• type def

typedef struct node
{
	tWord		*dataPtr;
	struct node	*llink; // backward pointer
	struct node	*rlink; // forward pointer
} NODE;

typedef struct
{
	int		count;
	NODE	*head;
	NODE	*rear;
} LIST;

• Insertion code

static int _insert(LIST* pList, NODE* pPre, tWord* dataInPtr)
{
	NODE* newNode = malloc(sizeof(NODE));
	if (!newNode) {
		fprintf(stderr, "ERROR: cannot create NODE\n");
		return 0;
	}

	newNode->dataPtr = dataInPtr;
	newNode->rlink = NULL;
	newNode->llink = NULL;

	// 1. pPre = NULL (empty or at begin)
	if (pPre == NULL)
	{
		newNode->llink = NULL;
		newNode->rlink = pList->head;
		pList->head = newNode;
		if (pList->count == 0) pList->rear = newNode;
		else newNode->rlink->llink = newNode;
	}
	//2. pPre !=NULL (in middle of at end)
	else
	{
		newNode->rlink = pPre->rlink;
		newNode->llink = pPre;
		if (pPre->rlink == NULL) pList->rear = newNode; //at end
		else newNode->rlink->llink = newNode;
		pPre->rlink = newNode;
	}
	

	return 1;
}

• Deletion code

static void _delete(LIST* pList, NODE* pPre, NODE* pLoc, tWord** dataOutPtr)
{
	*dataOutPtr = pLoc->dataPtr;
	// 1. pPre == NULL ( begin)
	if (pPre == NULL)
	{
		if (pLoc->rlink == NULL) { //if only 1 tWord in list
			pList->head = NULL;
			pList->rear == NULL;
		}
		else {
			pList->head = pLoc->rlink;
			pLoc->rlink->llink = NULL;
		}
	}
	// 2. pPre != NULL ( in middle or end)
	else
	{
		if (pLoc->rlink == NULL) // end of the list
		{
			pList->rear = pLoc->llink;
			pPre->rlink = NULL;
		}
		else //in middle
		{
			pPre->rlink = pLoc->rlink;
			pLoc->rlink->llink = pPre;
		}
	}
	free(pLoc);
	pList->count -= 1;
}

End of Doc.