원형 연결 리스트(Circular Linked List) 설명과 예제 코드(C++)

algorithm

단일, 양방향 연결 리스트에 이어서 원형 연결 리스트에 대해서 알아보겠습니다. 원형 링크드 리스트는 끝이 없고 리스트가 원형으로 순환하는 것을 말합니다. 끝이 없고 계속 순환하기 때문에 잘못하면 무한히 순환할 수 있습니다. 이 부분에 주의를 기울여 링크드 리스트를 구현해야 합니다. 원형 리스트는 CPU의 라운드 로빈 알고리즘과 같이 경우에 따라 유용하게 사용될 수 있습니다.

완성된 코드는 GitHub - Circualr Linked List에 있습니다. 코드만 참고하시는 분들은 GitHub를 확인해주세요.

단일, 양방향 리스트에 대한 내용은 아래 글을 참고해주세요.

원형 링크드 리스트 데이터 구조

링크드 리스트에 데이터가 저장되는 객체 1개를 노드(Node)라고 합니다. 코드로 이렇게 정의할 수 있습니다. 구조체 내부에는 데이터를 저장하는 data와 다음 노드의 주소를 저장하는 next변수가 있습니다.

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

그리고 링크드 리스트의 처음을 가리키는 head라는 변수가 있습니다. 데이터에 접근하려면 이 변수를 통해서 접근할 수 있습니다.

ListNode* head = NULL;

또한, 원형 링크드 리스트는 tail이라는 변수를 갖을 수 있습니다. 가장 마지막에 오는 변수의 주소를 저장하는 용도입니다. 이 글의 샘플 코드에서는 tail을 사용하지 않고 매번 마지막 노드를 구하도록 구현하였습니다. 리스트의 노드 개수가 매우 많다면 매번 tail을 구하는 것이 비효율적일 수 있습니다.

링크드 리스트의 모든 노드 출력

head를 입력받아 마지막 노드까지 출력할 수 있습니다. 마지막 노드의 다음 노드는 head를 가리키기 때문에, tail이 head와 같다면 이 노드가 마지막이라는 의미입니다.

void PrintList(ListNode* head) {
	if (head == NULL) {
		cout << "NULL\n";
		return;
	}
	ListNode* current = head;
	do {
		cout << current->data << " -> ";
		current = current->next;
	} while (current != head);
	cout << "HEAD\n";
}

링크드 리스트의 맨 앞에 노드 추가

맨 앞에 노드를 추가하는 것은 head의 위치에 노드를 추가한다는 의미입니다. 노드가 없을 때와 노드가 있을 때를 구분하여 데이터를 추가하도록 구현하였습니다. 이 글에서는 tail 전역 변수를 따로 만들지 않았기 때문에 필요할 때마다 tail을 계산하였습니다. head를 새로운 노드로 교체하고 tail이 새로운 head를 가리키는 것을 잊지 말아야 합니다.

void InsertAtBegin(ListNode * *head, int data) {
	ListNode* inserted = new ListNode;
	inserted->data = data;
	if (*head == NULL) {
		*head = inserted;
		inserted->next = *head;
	}
	else {
		ListNode* tail = *head;
		while (tail->next != *head) {
			tail = tail->next;
		}
		inserted->next = *head;
		*head = inserted;
		tail->next = *head;
	}
}

링크드 리스트의 맨 끝에 노드 추가

맨 뒤에 노드를 추가하는 것은 head는 변하지 않고, tail만 변경된다는 의미입니다. old tail은 new tail을 가리키도록, new tail은 head를 가리키도록 수정되어야 합니다.

void InsertAtEnd(ListNode * *head, int data) {
	ListNode* inserted = new ListNode;
	inserted->data = data;
	if (*head == NULL) {
		*head = inserted;
		inserted->next = *head;
	}
	else {
		ListNode* tail = *head;
		while (tail->next != *head) {
			tail = tail->next;
		}
		tail->next = inserted;
		inserted->next = *head;
	}
}

링크드 리스트의 맨 앞의 노드 삭제

노드 추가와 반대로, 노드를 삭제하는 코드를 작성하겠습니다. 맨 앞의 노드를 삭제하는 것은 head를 삭제하고 tail과 새로운 head를 연결해주는 것을 말합니다.

void DeleteFrontNode(ListNode * *head) {
	ListNode* removed = *head;
	if (*head == NULL) {
		return;
	}
	else {
		ListNode* tail = *head;
		while (tail->next != *head) {
			tail = tail->next;
		}
		if (tail == *head) {
			*head = NULL;
		}
		else {
			(*head) = (*head)->next;
			tail->next = *head;
		}
		delete(removed);
	}
}

링크드 리스트의 맨 마지막 노드 삭제

맨 마지막 노드를 삭제하는 것은 head는 변하지 않고, tail이 삭제되는 것을 말합니다. 새로운 tail이 head를 가리키도록 해야 합니다.

void DeleteFrontNode(ListNode * *head) {
	ListNode* removed = *head;
	if (*head == NULL) {
		return;
	}
	else {
		ListNode* tail = *head;
		while (tail->next != *head) {
			tail = tail->next;
		}
		if (tail == *head) {
			*head = NULL;
		}
		else {
			(*head) = (*head)->next;
			tail->next = *head;
		}
		delete(removed);
	}
}

완성된 코드

완성된 코드는 GitHub - Circualr Linked List에 있습니다.

main을 실행해보면 원형 링크드 리스트에서 노드가 생성되고 삭제되는 것을 볼 수 있습니다.

int main()
{
	InsertAtBegin(&head, 4);
	PrintList(head);
	InsertAtBegin(&head, 17);
	PrintList(head);
	InsertAtBegin(&head, 1);
	PrintList(head);
	InsertAtBegin(&head, 5);
	PrintList(head);

	InsertAtEnd(&head, 12);
	PrintList(head);
	InsertAtEnd(&head, 13);
	PrintList(head);
	InsertAtEnd(&head, 19);
	PrintList(head);
	InsertAtEnd(&head, 20);
	PrintList(head);

	DeleteFrontNode(&head);
	PrintList(head);
	DeleteFrontNode(&head);
	PrintList(head);
	DeleteFrontNode(&head);
	PrintList(head);
	DeleteFrontNode(&head);
	PrintList(head);

	DeleteLastNode(&head);
	PrintList(head);
	DeleteLastNode(&head);
	PrintList(head);
	DeleteLastNode(&head);
	PrintList(head);
	DeleteLastNode(&head);
	PrintList(head);
}

실행 결과는 다음과 같습니다.

4 -> HEAD
17 -> 4 -> HEAD
1 -> 17 -> 4 -> HEAD
5 -> 1 -> 17 -> 4 -> HEAD
5 -> 1 -> 17 -> 4 -> 12 -> HEAD
5 -> 1 -> 17 -> 4 -> 12 -> 13 -> HEAD
5 -> 1 -> 17 -> 4 -> 12 -> 13 -> 19 -> HEAD
5 -> 1 -> 17 -> 4 -> 12 -> 13 -> 19 -> 20 -> HEAD
1 -> 17 -> 4 -> 12 -> 13 -> 19 -> 20 -> HEAD
17 -> 4 -> 12 -> 13 -> 19 -> 20 -> HEAD
4 -> 12 -> 13 -> 19 -> 20 -> HEAD
12 -> 13 -> 19 -> 20 -> HEAD
12 -> 13 -> 19 -> HEAD
12 -> 13 -> HEAD
12 -> HEAD
NULL

참고

Loading script...
codechachaCopyright ©2019 codechacha