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

원형 연결 리스트 (Circular Linked List)

원형 연결 리스트는 마지막 노드가 첫 번째 노드를 가리키는 리스트입니다.

단순 연결 리스트는 마지막 노드의 link 필드가 NULL이라고 언급했습니다. 하지만, 원형 연결 리스트는 NULL이 아니라 첫 번째 노드 주소가 됩니다. 마지막 노드를 방문해도 첫 번째 노드로 가게 되고 모든 노드가 link 멤버에 NULL이 되어 있지 않은 상태로 연결되어 있는 상태가 됩니다.

 

이렇게 된다면 노드를 삽입할 때 상수 시간으로 고정이 된다는 장점이 있습니다. 기존에 단순 연결 리스트에서는 끝에 노드를 삽입하기 위해 리스트의 길이만큼 걸리게 되지만, 원형 연결 리스트에서는 헤드 포인터 자체를 옮겨버리면 되기 때문에 훨씬 적은 시간 안에 연산이 이루어지게 됩니다.

 

함수별로 어떻게 동작하는지 살펴보겠습니다.

 

*insert_first(*head, data)

원형 연결 리스트의 처음 부분에 노드를 삽입하는 과정은 다음과 같습니다.

1. 새로운 노드인 node를 동적으로 메모리 할당한다.
2. node의 data 멤버에 함수의 parameter로 넘어온 data 값을 넣어준다.
3. (헤드 포인터가 NULL이면)
4. node를 헤드 포인터가 가리키도록 하고,
5. 헤드 포인터가 node를 가리키도록 한다. 즉, 자기를 순환 참조하도록 만든다.
6. (그렇지 않으면)
7. 헤드 포인터가 가리키는 노드 ( == 제일 앞에 있는 노드 )가 가리키던 노드를 node가 가리키도록 하고
8. 헤드 포인터가 가리키는 노드 ( == 제일 앞에 있는 노드) 가 node를 가리킨다.

ListNode *insert_first(ListNode *head, element data) {
    ListNode *node = (ListNode *)malloc(sizeof(ListNode)); // 1.
    node->data = data; // 2.
    if(head == NULL) { // 3.
        head = node; // 4.
        node->link = head; // 5.
    } else { // 6.
        node->link = head->link; // 7.
        head->link = node; // 8.
    }
    return head;
}

 

*insert_last(*head, data)

원형 연결 리스트의 마지막 부분에 노드를 삽입하는 과정은 다음과 같습니다.

1. 새로운 노드인 node를 동적으로 메모리 할당한다.
2. node의 data 멤버에 함수의 parameter로 넘어온 data 값을 넣어준다.
3. (헤드 포인터가 NULL이면)
4. node를 헤드 포인터가 가리키도록 하고,
5. 헤드 포인터가 node를 가리키도록 한다. 즉, 자기를 순환 참조하도록 만든다.
6. (그렇지 않으면)
7. 헤드 포인터가 가리키는 노드 ( == 제일 앞에 있는 노드 )가 가리키던 노드를 node가 가리키도록 하고
8. 헤드 포인터가 가리키는 노드 ( == 제일 앞에 있는 노드) 가 node를 가리킨다.
9. node를 헤드 포인터가 가리킨다.

ListNode *insert_last(ListNode *head, element data) {
    ListNode *node = (ListNode *)malloc(sizeof(ListNode)); // 1.
    node->data = data; // 2.
    if(head == NULL) { // 3.
        head = node; // 4.
        node->link = head; // 5.
    } else { // 6.
        node->link = head->link; // 7.
        head->link = node; // 8.
        head = node; // 9.
    }
    return 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;
}

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