[Data Structure] 원형 연결 리스트

원형 연결 리스트 (Circular Linked List)

- 마지막 노드의 링크가 첫 번째 노드의 주소를 가리키는 리스트

- 하나의 노드에서 모든 노드에 접근 가능

- 헤드 포인터가 항상 마지막 노드를 가리키게 설정

 

 

1. 삽입 연산

① 리스트의 맨 앞에 삽입

• head == NULL인 경우 : new_node를 insert하게 되면 헤드 포인터가 new_node를 가리키게 된다

void insert_first(c_listnode** head, c_listnode* new_node) {
	// 리스트 맨 처음에 new_node 삽입
	if (*head == NULL) {
		// head가 NULL => 공백리스트 상태
		// new_node를 insert하게되면 head pointer는 new_node를 가리키게 된다
		*head = new_node;
		new_node->link = *head;
	}
	else { // 리스트의 맨 앞에 new_node 삽입
		new_node->link = (*head)->link;
		(*head)->link = new_node;
	}
}

 

② 리스트의 맨 뒤에 삽입

- 리스트의 맨 뒤 (head 뒤)에 new_node를 insert

• 헤드 포인터는 항상 리스트의 마지막 노드를 가리킨다
• 따라서, 헤드 포인터는 이제 new_node를 가리키게 된다 

void insert_last(c_listnode** head, c_listnode* new_node) {
	// 리스트 맨 끝(head 뒤에) new_node 삽입 -> new_node가 head가 된다
	if (*head == NULL) {
		// head가 NULL => 공백리스트 상태
		// new_node를 insert하게되면 head pointer는 new_node를 가리키게 된다
		*head = new_node;
		new_node->link = *head;
	}
	else {
		// 리스트의 맨 마지막 (head 뒤)에 new_node를 삽입
		// 헤드 포인터는 항상 리스트의 맨 마지막 노드를 가리킨다
		// 따라서, 헤드 포인터는 이제 new_node를 가리키게 된다
		new_node->link = (*head)->link;
		(*head)->link = new_node;
		*head = new_node;
	}
}

 

③ 리스트의 중간에 삽입

void insert_middle(c_listnode** head, c_listnode* pre, c_listnode* new_node) {
	if (pre == NULL) { 
		// 이전 노드가 NULL => 공백리스트 상태
		// new_node를 insert하게되면 head pointer는 new_node를 가리키게 된다
		*head = new_node;
		new_node->link = *head;
	}
	else { // pre노드 다음에 new_node 삽입
		new_node->link = pre->link;
		pre->link = new_node;
	}
}

 

 

 

2. 삭제 연산

void remove_node(c_listnode** head, c_listnode* pre, c_listnode* removed) {
	 if (pre == NULL) {
		 // pre == NULL ~> 현재 removed 노드만 존재하는 상태
		free(removed);
	}
	else {
		pre->link = removed->link;
		free(removed);
	}
}

 

 

3. 탐색 연산

c_listnode* search(c_listnode* head, element value) {
	c_listnode* p;
	if (head == NULL) return NULL;
	p = head;
	do {
		if (p->data == value) return p;
		p = p->link;
	} while (p != head);
	return NULL;
}

 

 

4. Full Code (Circular Linked List)

#include <stdio.h>
#include <stdlib.h>

typedef int element;

typedef struct {
	element data;
	struct c_listnode* link;
}c_listnode;

void insert_middle(c_listnode** head, c_listnode* pre, c_listnode* new_node) {
	if (pre == NULL) { 
		// 이전 노드가 NULL => 공백리스트 상태
		// new_node를 insert하게되면 head pointer는 new_node를 가리키게 된다
		*head = new_node;
		new_node->link = *head;
	}
	else { // pre노드 다음에 new_node 삽입
		new_node->link = pre->link;
		pre->link = new_node;
	}
}

void insert_first(c_listnode** head, c_listnode* new_node) {
	// 리스트 맨 처음에 new_node 삽입
	if (*head == NULL) {
		// head가 NULL => 공백리스트 상태
		// new_node를 insert하게되면 head pointer는 new_node를 가리키게 된다
		*head = new_node;
		new_node->link = *head;
	}
	else { // 리스트의 맨 앞에 new_node 삽입
		new_node->link = (*head)->link;
		(*head)->link = new_node;
	}
}

void insert_last(c_listnode** head, c_listnode* new_node) {
	// 리스트 맨 끝(head 뒤에) new_node 삽입 -> new_node가 head가 된다
	if (*head == NULL) {
		// head가 NULL => 공백리스트 상태
		// new_node를 insert하게되면 head pointer는 new_node를 가리키게 된다
		*head = new_node;
		new_node->link = *head;
	}
	else {
		// 리스트의 맨 마지막 (head 뒤)에 new_node를 삽입
		// 헤드 포인터는 항상 리스트의 맨 마지막 노드를 가리킨다
		// 따라서, 헤드 포인터는 이제 new_node를 가리키게 된다
		new_node->link = (*head)->link;
		(*head)->link = new_node;
		*head = new_node;
	}
}

void remove_node(c_listnode** head, c_listnode* pre, c_listnode* removed) {
	 if (pre == NULL) {
		 // pre == NULL ~> 현재 removed 노드만 존재하는 상태
		free(removed);
	}
	else {
		pre->link = removed->link;
		free(removed);
	}
}

c_listnode* search(c_listnode* head, element value) {
	c_listnode* p;
	if (head == NULL) return NULL;
	p = head;
	do {
		if (p->data == value) return p;
		p = p->link;
	} while (p != head);
	return NULL;
}

void print_list(c_listnode* head) {
	c_listnode* p;
	if (head == NULL) {
		printf("Error : List is empty\n\n");
		return;
	}
	p = head->link;
	while (p != head) {
		printf("%d -> ", p->data);
		p = p->link;
	}
	 printf("%d -> \n\n", p->data); // 마지막 노드
}

int main(void) {
	c_listnode* head = NULL;
	c_listnode* p1 = (c_listnode*)malloc(sizeof(c_listnode));
	p1->data = 10; p1->link = NULL;
	c_listnode* p2 = (c_listnode*)malloc(sizeof(c_listnode));
	p2->data = 30; p2->link = NULL;
	c_listnode* p3 = (c_listnode*)malloc(sizeof(c_listnode));
	p3->data = 50; p3->link = NULL;
	c_listnode* p4 = (c_listnode*)malloc(sizeof(c_listnode));
	p4->data = 70; p4->link = NULL;
	c_listnode* p5 = (c_listnode*)malloc(sizeof(c_listnode));
	p5->data = 90; p5->link = NULL;
	c_listnode* p6 = (c_listnode*)malloc(sizeof(c_listnode));
	p6->data = 110; p6->link = NULL;
	c_listnode* p7 = (c_listnode*)malloc(sizeof(c_listnode));
	p7->data = 10000; p7->link = NULL;

	print_list(head);

	printf("\n>>> insert p1(10)\n");
	insert_middle(&head, NULL, p1); // p1(head)
	print_list(head);

	printf("\n>>> insert_first p2(30)\n");
	insert_first(&head, p2); // p2->p1(head)
	print_list(head);

	printf("\n>>> insert_first p3(50)\n");
	insert_first(&head, p3); // p3->p2->p1(head)
	print_list(head);

	printf("\n>>> insert_last p4(70)\n");
	insert_last(&head, p4); // p3->p2->p1->p4(head)
	print_list(head);

	printf("\n>>> insert p5(90) pre : p2(30)\n");
	insert_middle(&head, p2, p5); // p3->p2->p5->p1->p4(head)
	print_list(head);

	printf("\n>>> insert p6(110) pre : p1(10)\n");
	insert_middle(&head, p1, p6); // p3->p2->p5->p1->p6->p4(hear)
	print_list(head);

	printf("\n>>> remove p1(10) pre : p5(90)\n");
	remove_node(&head, p5, p1); // p1(10)삭제 : p3->p2->p5->p6->p4(head)
	print_list(head);

	printf("\n>>> insert_last p7(10000)\n");
	insert_last(&head, p7); // p3->p2->p5->p6->p4->p7(head)
	print_list(head);

	if (search(head, 50) != NULL)
		printf("리스트에 50이 있습니다!!\n\n");
	else
		printf("리스트에 50이 없습니다.\n\n");
	if (search(head, 75) != NULL)
		printf("리스트에 75가 있습니다!!\n\n");
	else
		printf("리스트에 75가 없습니다.\n\n");
	if (search(head, 10000) != NULL)
		printf("리스트에 10000이 있습니다!!\n\n");
	else
		printf("리스트에 10000이 없습니다.\n\n");
}