[자료구조] 원형 연결 리스트 (Circular Linked List) 의 구조와 구현

 

원형 연결 리스트의 구조

 

- 마지막 노드가 첫번째 노드를 가리키게 하여 리스트의 구조를 원형으로 만든 연결 리스트

     => 마지막 노드의 링크필드가 NULL 이 아닌, 첫번째 노드의 주소이다.

 

 

ㅇ

 

 

장점
- 하나의 노드에서 다른 모든 노드로의 접근이 가능

- 하나의 노드에서 링크를 계속 따라가면 결국 모든 노드를 거쳐 자기 자신으로 되돌아오는 것이 가능

- 노드의 삽입과 삭제가 단순 연결 리스트보다는 용이함

- 특히, 리스트의 끝에 노드를 삽입하는 연산이 단순 연결리스트보다 효율적 -> 헤드 포인터에서 시작하여 모든 노드를 거쳐 마지막에 삽입하는 것이 아니라, 헤드포인터가 마지막 노드를 가리키도록 구성하면 리스트의 처음과 끝에 노드를 삽입할 수 있다.

 

 

가장 최근에 추가되었던 30 데이터를 가지고 있는 노드의 주소를 헤드포인터 값으로 변경하면, 다음에 삽입될 때에는, 이 노드 다음에 삽입이 된다.

 

 

 

---

원형 연결 리스트의 구현

 

헤드포인터 head는 항상 마지막 노드를 가리키고 있다!

- (head==마지막 노드주소, head->link==첫번째 노드주소)

 

 

 

 

원형 연결 리스트의 삽입 연산

- 마지막 노드의 링크를 첫번째 노드로 연결

- 공백 리스트인 경우: 삽입하는 노드가 리스트의 첫번째 노드이자 마지막 노드이다. (링크에 NULL값이 아닌 자기 자신의 주소를 대입)

 

 

 

 

원형 리스트의 처음에 삽입

 

- 새로운 노드의 링크인 node->link가 첫번째 노드를 가리키게 하고 마지막 노드의 링크가 node를 가리키게 하면 된다.

- 그리고 head는 마지막 노드를 가리키도록 !

- 헤드 포인터가 

 

ListNode* insert_first(ListNode* head, element data) {
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	node->data = data;

	if (head == NULL) {
		head = node;
		node->link = head; // 새로 삽입된 첫번째 노드의 링크는 다시 자기 자신(head)을 가리키도록
	}
	else {
		node->link = head->link;
		head->link = node;
	}
	return head; // 변경된 헤드포인터 반환
}

 

 

 

 

 

원형 리스트의 끝에 삽입

 

- head의 위치만 새로운 노드로 바꾸어주면 새로운 노드가 마지막 노드가 된다.

(마지막에 head포인터가 새로 삽입된 node의 주소를 가리키도록 변경하면 된다.)

 

 

ListNode* insert_first(ListNode* head, element data) {
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	node->data = data;

	if (head == NULL) {
		head = node;
		node->link = head; // 새로 삽입된 첫번째 노드의 링크는 다시 자기 자신(head)을 가리키도록
	}
	else {
		node->link = head->link;
		head->link = node;
		head = node; // head의 위치만 새로운 노드로 바꾸어줌 -> 새로운 노드가 마지막 노드가 됨
	}
	return head; // 변경된 헤드 포인터 반환
}

 

 

 ** head 포인터가 가리키는 값이 변경되므로, 바뀐 첫번째 헤드 포인터를 리턴해주어야만 함수를 호출한 곳에서도 정상적으로 원형 리스트에 접근이 가능해진다.

** 만약 반환형이 없는 void 함수로 구현하고자 하면, 다음과 같이 head를 이중포인터로 받아 insert 함수 내에서 포인터값을 변경하도록 하면 된다.

 

void insert_last(ListNode** head, element data) {
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	node->data = data;

	if (*head == NULL) {
		*head = node;
		node->link = *head; // 새로 삽입된 첫번째 노드의 링크는 다시 자기 자신(head)을 가리키도록
	}
	else {
		node->link = (*head)->link;
		(*head)->link = node;
		(*head) = node; // head의 위치만 새로운 노드로 바꾸어줌 -> 새로운 노드가 마지막 노드가 됨
	}
}

 

 

---

원형 연결리스트 출력

 

- 앞서 head포인터는 마지막 노드의 주소를 의미한다고 설명했으므로, 첫번째 노드부터 순회하여 출력하도록 하려면, head->link 부터 접근해야 한다.

- 그리고 마지막 노드의 링크에는 NULL이 아닌, 첫번째 노드의 주소가 들어있으므로 while문이 아닌 do-while문을 사용해서 다시 첫번째 노드로 돌아온 경우 반복문을 빠져나가도록 해야 한다. (while문을 사용하게 되면 첫번째 조건에서 조건을 만족하지 못해 접근이 불가능하다)

 

void print_list(ListNode* head) {
	ListNode* p = head->link;

	if (head == NULL) return;
	do {
		printf("%d ", p->data);
		p = p->link;
	} while (p != head->link); // 첫번째 노드 head->link에 도달하면 마지막 노드

	printf("\n");
}

 

 

---

 

테스트 프로그램

 

1과 2를 원형 리스트의 마지막에 삽입하고, 3을 원형 리스트의 처음에 삽입한 후에, 출력해보자.

 

 

 

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

typedef int element;
typedef struct ListNode {
	element data;
	struct ListNode* link;
}ListNode;

ListNode* insert_first(ListNode* head, element data) {
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	node->data = data;

	if (head == NULL) {
		head = node;
		node->link = head; // 새로 삽입된 첫번째 노드의 링크는 다시 자기 자신(head)을 가리키도록
	}
	else {
		node->link = head->link;
		head->link = node;
	}
	return head; // 변경된 head포인터 반환
}

ListNode * insert_last(ListNode* head, element data) {
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	node->data = data;

	if (head == NULL) {
		head = node;
		node->link = head; // 새로 삽입된 첫번째 노드의 링크는 다시 자기 자신(head)을 가리키도록
	}
	else {
		node->link = head->link;
		head->link = node;
		head = node; // head의 위치만 새로운 노드로 바꾸어줌 -> 새로운 노드가 마지막 노드가 됨
	}
	return head; // 변경된 head포인터 반환
}

void insert(ListNode* head, ListNode* pre, element data) {
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	node->data = data;

	if (head == NULL) {
		head = node;
		node->link = head; // 새로 삽입된 첫번째 노드의 링크는 다시 자기 자신(head)을 가리키도록
	}
	else {
		node->link = pre->link;
		pre->link = node;
	}
	return head; // 변경된 head포인터 반환
}

void print_list(ListNode* head) {
	ListNode* p = head->link;

	if (head == NULL) return;
	do {
		printf("%d -> ", p->data);
		p = p->link;
	} while (p != head); // 첫번째 노드 head->link에 도달하면 마지막 노드
	printf("%d\n", p->data);
	printf("\n");
}

int main() {

	ListNode* phead=NULL;

	phead=insert_last(phead, 1); // 1
	phead=insert_last(phead, 2); // 1 2 
	phead=insert_first(phead, 3); // 3 1 2
	print_list(phead);
}

 

위에서 print_list에서는 마지막 노드(head)에 도달하면 반복문을 종료하도록 하였고,

마지막 노드에는 끝에 '->' 를 붙이지 않도록 반복문 밖에서 출력하도록 하였다.