[자료구조] 환형 링크드 리스트(Circular Linked List)

환형 링크드 리스트(Circular Linked List)

 

환형 링크드 리스트란?

• 단일 연결 리스트로 구현 시 Tail의 다음 노드 포인터가 Head를 가리킴
• 이중 연결 리스트로 구현 시 Tail의 다음 노드 포인터가 Head이고 Head의 이전 노드 포인터는 Tail을 가르킨다.
• 데이터의 추가, 삽입, 삭제는 용이하나 그 과정까지 탐색 속도가 떨어진다.
• 머리와 꼬리가 서로 연결되어있기때문에 중간의 어디서든 탐색이 가능해진다.

헤드의 이전노드는 테일을 가르키고 테일의 다음노드는 헤드를 가르킨다

저는 생성자에서 이를 미리 연결 시켜놨습니다.

LinkedList::LinkedList()
{
	Head = new Node();
	Tail = new Node();
	Head->Next = Tail;
	Head->Prev = Tail;
	Tail->Next = Head;
	Tail->Prev = Head;
}

환영 링크드 리스트 구현

• 노드 추가
• 노드 탐색
• 노드 삭제
• 노드 삽입

구현시 더블링크드 리스트와 거의 차이가 없다.

노드 추가

더블 링크드 리스트와 차이가 없다.

void LinkedList::Add(const int& NewData)
{
	Node* NewNode = new Node();

	if (NewNode != nullptr && Tail != nullptr)
	{
		NewNode->Data = NewData;
		NewNode->Prev = Tail->Prev;
		NewNode->Next = Tail;
		Tail->Prev->Next = NewNode;
		Tail->Prev = NewNode;
	}
}

 

노드 탐색

더블 링크드 리스트와 차이가 없다. 단지 어디서든 탐색이 가능해진다.

Node* LinkedList::Search(const int& Data)
{
	Node* CurrentNode = Head;

	if (CurrentNode != nullptr)
	{
		while (CurrentNode->Next != Tail)
		{
			if (CurrentNode->Next->Data == Data)
			{
				return CurrentNode->Next;
			}

			CurrentNode = CurrentNode->Next;
		}
		std::cout << "검색 할 노드가 없습니다" << std::endl;
		return nullptr;
	}
	else
	{
		std::cout << "헤드가 없습니다" << std::endl;
		return nullptr;
	}
}

 

노드 삭제

더블 링크드 리스트와 차이가 없다.

void LinkedList::Remove(Node* InRemoveNode)
{
	Node* CurrentNode = Head->Next;
	if (CurrentNode != nullptr && InRemoveNode != nullptr)
	{
		if (CurrentNode == InRemoveNode)
		{
			Head->Next = InRemoveNode->Next;
			InRemoveNode->Next->Prev = Head;
		}
		else
		{
			InRemoveNode->Prev->Next = InRemoveNode->Next;
			InRemoveNode->Next->Prev = InRemoveNode->Prev;
		}
		std::cout << InRemoveNode->Data << "제거" << std::endl;
		delete InRemoveNode;
	}
}

 

노드 삽입

더블 링크드 리스트와 차이가 없다.

 

void LinkedList::Insert(const int& NewData, const int& Index)
{
	Node* CurrentNode = Head;

	if (CurrentNode != nullptr)
	{
		for (int i = 0; i < Index; ++i)
		{
			if (CurrentNode != nullptr)
			{
				CurrentNode = CurrentNode->Next;
			}
			else
			{
				std::cout << Index << "번째의 노드가 없습니다" << std::endl;
				return;
			}
		}
	}

	if (CurrentNode == nullptr)
	{
		std::cout << Index << "번째의 노드가 없습니다" << std::endl;
		return;
	}

	Node* NewNode = new Node();
	if (NewNode != nullptr)
	{
		NewNode->Data = NewData;

		CurrentNode->Next->Prev = NewNode;
		NewNode->Next = CurrentNode->Next;
		NewNode->Prev = CurrentNode;
		CurrentNode->Next = NewNode;
	}
}

메인 코드

int main()
{
	LinkedList* List = new LinkedList();

	if (List != nullptr)
	{
		List->Add(5);
		List->Add(9);
		List->Add(7);
		List->Insert(3, 1);
		List->Show();
		Node* RemoveNode = List->Search(9);
		if (RemoveNode != nullptr)
		{
			List->Remove(RemoveNode);
		}
		List->Show();
	}
}

리스트에 5,9,7을 add함수를통해 넣어주고 1번째뒤에 3을 넣어주면 5 3 9 7이 된다.

헤드와 테일에는 0으로 초기화를 해주었고 이를 Show함수를통해 출력을 한다.

void LinkedList::Show()
{
	Node* CurrentNode = Head->Next;

	if (CurrentNode != nullptr)
	{
		while (1)
		{
			std::cout << CurrentNode->Data << std::endl;
			CurrentNode = CurrentNode->Next;
			Sleep(1000.f);
		}
	}
}

Sleep함수를 통해 1초마다 실행되게 하고 다음노드를 계속 출력해주는 코드이다.

이러면 0 5 3 9 7 0 이 반복적으로 출력된다.