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

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

---

단일 연결 리스트로 만들어진 원형 연결 리스트

원형 연결 리스트는 마지막 꼬리(Tail)가 NULL을 가리키지 않고 처음 머리(Head)를 가리키는 구조이다. 단일 연결 리스트와 이중 연결 리스트 둘 다 구현이 가능하다.

이중 연결 리스트로 만들어진 원형 연결 리스트

원형 연결 리스트는 한 노드에서 모든 노드로 접근이 가능할 수 있다는 장점을 가지고 있다. 하지만 잘못 사용 시 무한 순환이 되는 상황이 발생할 수 있습니다.

소스코드 구현 (C++)

#include <iostream>

using namespace std;

struct Node
{
	Node(int data)
	{
		Data = data;
		Prev = Next = NULL;
	}

	void Destroy()
	{
		delete this;
	}
	Node* Prev;
	int Data;
	Node* Next;
};

class CircularLinkedList
{
public:
	CircularLinkedList()
	{
		Head = Tail = NULL;
		Size = 0;
	}
	//맨뒤에 삽입
	void Push_back(Node* node)
	{
		//Head가 비었을 경우
		if (Head == NULL)
		{
			Head = node;
			Tail = node;
			Head->Next = node;
			Head->Prev = node;
			Size++;
		}
		//그 외
		else
		{
			Tail->Next->Prev = node;
			Tail->Next = node;

			node->Prev = Tail;
			node->Next = Head;
			Tail = node;
			Size++;
		}
	}
	//원하는 노드 뒤에 삽입 (cur) -> (node) -> (cur->Next)
	void Insert(Node* cur, Node* node)
	{
		node->Next = cur->Next;
		node->Prev = cur;

		cur->Next->Prev = node;
		cur->Next = node;

		Size++;
	}
	//제거
	void Remove(Node* node)
	{
		if (node == Head)
		{
			Head->Prev->Next = node->Next;
			Head->Next->Prev = node->Prev;

			Head = node->Next;

			node->Destroy();
		}
		else
		{
			Node* n = Head;
			while (n != node)
			{
				n = n->Next;
			}
			if (n == Tail)
			{
				Tail->Prev->Next = Head;
				Tail->Next->Prev = Tail->Prev;

				Tail = node->Prev;
				
				node->Destroy();
			}
			else
			{
				n->Prev->Next = n->Next;
				n->Next->Prev = n->Prev;

				node->Destroy();
			}
		}
		Size--;
	}
	int Search(Node* node)
	{
		Node* n = Head;
		int count = 0;
		while (n->Next != NULL)
		{
			if (n == node)
			{
				return count;
			}
			count++;
			n = n->Next;
		}
		return -1;
	}
	int GetSize()
	{
		return Size;
	}
	void PrintAll()
	{
		if (Size == 0) std::cout << "List is empty!!" << std::endl;
		else
		{
			std::cout << "Head[" << Head->Data << "],Tail[" << Tail->Data << "], Size[" << GetSize() << "] [";
			Node* head = Head;
			while (head)
			{
				std::cout << head->Data;
				if (head != Tail)
				{
					std::cout << " - ";
				}
				else if (head == Tail)
				{
					std::cout << " - " << Tail->Next->Data;
				}
				head = head->Next;
				if (Head == head) break;
			}
			std::cout << "]" << std::endl;
		}
	}
public:
	Node* Head;
	Node* Tail;
	int Size;
};

int main()
{
	CircularLinkedList DL;
	//Create Node
	Node* node0 = new Node(0);
	DL.Push_back(node0);
	Node* node1 = new Node(1);
	DL.Push_back(node1);
	Node* node2 = new Node(2);
	DL.Push_back(node2);
	Node* node3 = new Node(3);
	DL.Push_back(node3);

	DL.PrintAll();
	
	return 0;
}

출력 결과

삽입/제거

//중간 삽입
Node* node7 = new Node(7);
DL.Insert(node1, node7);

DL.PrintAll();
	
//제거
DL.Remove(node7);

DL.PrintAll();

출력 결과

헤드/꼬리 제거

//헤드 제거
DL.Remove(node0);

DL.PrintAll();
	
//꼬리 제거
DL.Remove(node3);

DL.PrintAll();

출력 결과

---

이중 연결 리스트로 원형 연결 리스트를 만들어 보았다. 이것을 출력해보았을 때 특정 break지점을 만들어 주지 않으면 무한적으로 순회하는 형태를 확인할 수 있었는데 이것을 이용하여 지속적으로 출력해야하는 형태를 구현할 때 상당히 유용할 것 같다는 생각이 들었다.