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

 

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

 

선형 자료 구조 중 "원형 연결 리스트"에 대해 알아보겠습니다.

 

---

 

Overview

 

1. 원형 연결 리스트
2. 삽입, 제거 알고리즘

 

원형 연결 리스트

1. 원형 연결 리스트

• 원형 연결 리스트는 연결 리스트의 마지막 노드가 "nullptr" 가리키지 않고, 연결 리스트의 첫 번째 노드를 가리키는 자료구조입니다. 

 

삽입, 삭제 알고리즘

1. 삽입

#include <iostream>
#include <string>
using namespace std;

typedef struct _Node {
	string Name;
	struct _Node* Next;
}Node;

int main()
{
    	Node* Head;

	Node* Node_1 = new Node();
	Node_1->Name = "First";

	// 1. 최초의 원형 리스트 생성
	if (Head->Next == nullptr)
	{
		Head = Node_1;

		// 주의! nullptr가 아니라 다시 Head를 가리킵니다.
		Node_1->Next = Head;
	}

	// 2. 원형 리스트의 삽입
	Node* Node_2 = new Node();
	Node_2->Name = "Second";

	Node_2->Next = Node_1->Next;
	Node_1->Next = Node_2;
    
}

 

Details

 

• 원형 연결 리스트의 삽입 알고리즘은 단일 연결 리스트의 것과 크게 다름이 없습니다.
• 다만, 리스트의 끝 단에 위치할 노드의 "링크 포인터"가 nullptr를 가리키는지, Head를 가리키는지 눈여겨봐야 합니다.

 

2. 삭제

int main()
{
 	//...
    
 	// 원형 리스트의 삭제
	Node_1->Next = Node_2->Next;
	Node_2->Next = nullptr;
	Node_2->Name.clear();

	delete Node_2;
    
   	//...
}

 

Details

 

1. 원형 연결 리스트의 삭제 알고리즘은 '더' 간단합니다.
2. 삭제할 노드의 이전 노드에게 다음 노드를 가리키는 포인터를 전달해주고, 연결을 끊어버리면 됩니다.