원형 연결 리스트

원형 연결 리스트

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

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

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

 

- 리스트의 끝에 노드를 삽입하는 연산이 단순 연결 리스트보다 효율적

- 단순 연결 리스트에서 리스트의 끝에 노드를 추가하려면 head에서부터 링크를 따라 노드 개수만큼 진행

- 원형 연결 리스트에서는 아래와 같이 헤드 포인터가 마지막 노드를 가리키도록 구성하여 효율적인 처리 가능

- 헤드 포인터 head가 마지막 노드를 가리키고 있음

- 첫 번째 노드는 head->link가 가리키고 있음

- 리스트의 마지막에 노드를 삽입하거나 삭제하기 위해 리스트의 끝까지 갈 필요 x

---

원형 연결 리스트 정의

- 원칙적으로 헤드 포인터만 있으면 됨

ListNode* head;

---

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

- node는 새로운 노드

- node->link가 첫 번째 노드(10)를 가리키게 함

- 마지막 노드의 링크가 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;
	}
	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;
	}
	else {
		node->link = head->link;
		head->link = node;
		head = node;
	}
	return head;
}

---

전체 프로그램

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

typedef int element;
typedef struct {
	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;
	}
	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;
}
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->link);
}

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;
}

>>