[Data Structure] #Circular Linked List - C언어

원형 연결리스트란?

단순 연결리스트는 마지막 노드가 NULL을 가르키고 있는 반면에, 원형 연결리스트는 마지막 노드가 맨 처음 노드를 가르킵니다. 따라서 모든 노드를 순회할 수 있습니다.

단순 연결리스트의 마지막에 노드를 삽입하려고 하면 head부터 O(n)만큼의 검색을 해야하는데 원형 연결리스트의 경우는 head가 마지막 노드를 가르키기 때문에 단순 연결리스트보다 더 용이하게 노드를 삽입, 삭제할 수 있습니다.

• 원형 연결리스트는 모든 노드를 순회할 수 있다.
• 원형 연결리스트는 마지막 노드를 삽입, 삭제할 때 단순 연결 리스트처럼 맨 앞의 헤드 포인터부터 검색하지 않아도 된다.
• 원형 연결리스트의 헤드 포인터는 마지막 노드를 가르킨다.

구현

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

typedef struct ListNode {
	int data;
	struct ListNode* next;
} ListNode;

ListNode* insert_first(ListNode* head, int data) {
	ListNode *node = (ListNode*)malloc(sizeof(ListNode));
	node->data = data;
	if (head == NULL) {
		head = node;
		head->next = head;
	} else {
		node->next = head->next;
		head->next = node;
	}
	return head;
}

ListNode* insert_last(ListNode *head, int data) {
	ListNode *node = (ListNode*)malloc(sizeof(ListNode));
	node->data = data;
	if (head == NULL){
		head = node;
		node->next = head;
	} else {
		node->next = head->next;
		head->next = node;
		head = node;
	}
	return head;
}

void print_list(ListNode* head) {
	ListNode *p;
	if (head == NULL) return;
	p = head->next;

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

	printf("%d", head->data);
}

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

  head = insert_first(head, 10);
  head = insert_first(head, 20);
  head = insert_first(head, 30);
  head = insert_last(head, 100);
  head = insert_last(head, 200);
  head = insert_last(head, 300);
  print_list(head);
  return 0;
}