원형 연결 리스트

원형 연결 리스트란 리스트의 마지막 노드의 링크가 NULL이 아닌 첫 번째 노드 주소가 되는 리스트이다.

원형 연결 리스트의 장점이라면 한 노드에서 다른 모든 노드로의 접근이 가능하다는 것이다.

하나의 노드에서 링크를 계속 따라가면 결국 모든 노드를 거쳐서 자기 자신으로 되돌아올 수 있으므로 어떤 노드로도 갈 수 있다.

따라서 노드의 삽입과 삭제가 단순 연결 리스트보다는 용이해진다.

삭제나 삽업 시에는 항상 선행 노드의 포인터가 필요함을 기억하라.

원형 연결 리스트가 특히 유용한 경우는 리스트의 끝에 노드를 삽입하는 연산이 단순 연결 리스트보다 효율적일 수 있다는 것이다.

단순 연결 리스트에서 리스트의 끝에 노드를 삽입하려면 첫 번째 노드에서부터 링크를 따라서 노드의 개수만큼 진행하여 마지막 노드까지 간 다음에야 삽입할 수 있다.

그러나 만약 원형 연결 리스트에서 다음과 같이 헤드 포인터가 마지막 노드를 가리키도록 구성한다면 상수 시간 안에 리스트의 처음이나 끝에 노드를 삽입할 수 있다.

이 변형된 원형 연결 리스트를 이용하여 리스트의 처음에 삽입하는 함수를 작성하여보자.

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

헤드 포인터인 head가 마지막 노드를 가리키는 것만 기억하면 소스를 이해하는 데 별 문제가 없을 것이다.

void insert_first(ListNode** phead,ListNode* node) {

	if (*phead == NULL) {
		*phead = node;
		node->link = node;
	}

	else {
		node->link = (*phead)->link;
		(*phead)->link = node;
	}
}

위의 알고리즘에 한 문장만 추가하면 원형 연결 리스트의 마지막에 삽입할 수 있다.

즉, 원형 연결 리스트는 어차피 원형으로 연결되어 있으므로 어디가 처음이고 어디가 끝인지가 불분명하다.

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

void insert_last(ListNode** phead, ListNode* node) {
	if (*phead == NULL) {
		*phead = node;
		node->link = node;
	}

	else {
		node->link = (*phead)->link;
		(*phead)->link = node;
		*phead = node;
	}
}

테스트 프로그램

원형 리스트는 이와 같은 장점이 있지만 display 함수의 구현에서 보듯이 마지막 노드의 링크가 NULL이 아니기 때문에 리스트의 끝에 도달했는지를 검사하려면 헤드 포인터와 비교해야 한다.

또한 while 대신에 do-while 루프를 사용해야 한다.

#include <stdio.h>

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

void error(char* message) {
	fprintf(stderr, "%s\n", message);
	exit(1);
}

ListNode* create_node(element data, ListNode* link) {
	ListNode* new_node;
	new_node = (ListNode*)malloc(sizeof(ListNode));
	if (new_node == NULL) error("메모리 할당 에러");
	new_node->data = data;
	new_node->link = link;

	return new_node;
}

void display(ListNode* head) {

	ListNode* p;
	if (head == NULL)return;
	else head = head->link;

	p = head;
	do {
		printf("%d->", p->data);
		p = p->link;
	} while (p != head);
}

void insert_first(ListNode** phead,ListNode* node) {

	if (*phead == NULL) {
		*phead = node;
		node->link = node;
	}

	else {
		node->link = (*phead)->link;
		(*phead)->link = node;
	}
}

void insert_last(ListNode** phead, ListNode* node) {
	if (*phead == NULL) {
		*phead = node;
		node->link = node;
	}

	else {
		node->link = (*phead)->link;
		(*phead)->link = node;
		*phead = node;
	}
}

int main() {

	ListNode* list1 = NULL;

	insert_first(&list1, create_node(10, NULL));
	insert_first(&list1, create_node(20, NULL));
	insert_last(&list1, create_node(30, NULL));

	display(list1);

	return 0;
}