[자료구조] 원형 연결리스트 Circular Linked List

원형 연결리스트 

원형 연결리스트에서 head 포인터는 마지막 노드를 가리키게 됩니다. 이러한 방식의 원형 리스트는 head는 마지막 노드를, head의 link는 첫 노드를 가리키므로 리스트의 처음이나 마지막에 노드를 삽입하는 연산이 편리해집니다. 

 

 

앞부분 삽입 연산

 

노드를 리스트의 첫 부분에 삽입하는 연산의 경우 두 가지의 변경 사항이 필요합니다.

1. node의 link를 head의 link로 할당

2. head의 link를 node로 할당

 

[중요] 이때 순서가 변경되어서는 안됩니다. 만약 2를 먼저 실행, 즉 head의 link를 먼저 변경해버리면 node의 link를 지정해 줄 주소를 알 수 없게됩니다.

 

// 앞 삽입
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;
}

 

 

뒷부분 삽입 연산

 

 

리스트의 뒷부분에 삽입하는 경우 다음 세 가지의 변경 사항이 필요합니다.

1. node의 link를 head의 link로 할당

2. head의 link를 node로 할당

3. head를 node로 할당

 

[중요] 마찬가지로 순서가 변경되어서는 안됩니다. 중간 과정이 먼저일어나면 지정할 주소를 잃어버리게 됩니다.

 

// 뒷부분 삽입
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;

// 리스트의 항목 출력
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); // 마지막 노드
}
// 앞부분 삽입
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;
}
// 뒷부분 삽입
istNode* 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;	// 변경된 헤드 포인터 반환
}
// 메인
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;
}
/* 실행결과
10->20->30->40->
*/

 

 

연습문제

원형 연결 리스트에서 특정한 값을 탐색하는 함수를 작성하라

ListNode *search(ListNode *head, element data)

// 특정한 값 탐색
ListNode* search(ListNode* head, element data) {
	ListNode* p;
	if (head == NULL) return NULL;
	p = head->link;
	do {
		if (p->data == data) return p;  
		p = p->link;
	} while (p != head);
	return NULL;
}

 

원형 연결 리스트에 저장된 데이터의 개수를 반환하는 함수를 작성하라

int get_size(ListNode *head)

// 저장된 데이터 개수 반환
int get_size(ListNode* head) {
	ListNode* p;
	int count = 0;
	if (head == NULL) return 0;
	p = head->link;
	count++;
	while (p != head) {
		count++;
		p = p->link;
	}
	return count;
}