리스트(원형 리스트)

원형 연결리스트

원형 연결 리스트란 마지막 노드가 첫 번째 노드를 가리키는 리스트이다. 즉, 마지막 노드의 링크 필드가 널이 아니라 첫 번째 노드 주소가 되는 리스트이다.

원형리스트의 장점은 하나의 노드에서 다른 모든 노드로의 접근이 가능하다. 하나의 노드에서 링크를 계속 따라 가면 결국 모든 노드를 거쳐서 자기 자신으로 되돌아 올 수 있는 것이다.

보통 헤드포인터가 마지막 노드를 가르키게끔 구성하면 리스트의 처음이나 마지막에 노드를 삽입하는 연산이 단순 연결 리스트에 비하여 용이하다.

---

원형 연결 리스트의 처음에 삽입 연산

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

	if (head == NULL) { 
		head = node;
		node->link = head; 
	}
	else {
		node->link = head->link; head->link = node;
	}

		return 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; 
	}
	else {
		node->link = head->link; head->link = node;
		head = node;
	}
	return head; // 변경된 헤드 포인터를 반환한다. 
}

---

전체 코드

#include <stdio.h> 
#include <stdlib.h>
typedef int element; 

typedef struct ListNode { // 노드 타입
	element data;
	struct ListNode *link; 
} ListNode;

// 리스트의 항목 출력
void print_list(ListNode* head) { 
	ListNode* p;
	if (head == NULL) 
		return; 
	p = head->link;
	do {
		printf("%d->", p->data);
		p = p->link;
	} while (p != head);
	printf("%d->", p->data); // 마지막 노드 출력
}

int main(void) { 
	ListNode *head = NULL;

	// list = 10->20->30->40
	head = insert_last(head, 20); 
	head = insert_last(head, 30); 
	head = insert_last(head, 40); 
	head = insert_first(head, 10); 
	print_list(head);
	return 0;
}