[자료구조] Circle Linked List

📌 원형 연결 리스트

• 원형으로 순환되는 리스트
  
• 일반 연결리스트에서 마지막 노드가 nullptr이 아닌 첫번째 노드와 연결되는 리스트
  
• 원형 연결 리스트는 앞 뒤 구분이 없기 때문에 head를 기준으로 판별
  

• head가 가리키는 곳이 마지막, head -> next가 첫번째 노드
• 끝이 없는 구조이다 (끝에 도달한다는 개념이 없어서 무한순회 가능)
  

🟥 head 는 항상 마지막 노드를 가리키고 있다!
🟥 head -> next = 첫번째 노드

원형 연결리스트

-> 단방향 원형 연결 리스트
-> 양방향 원형 연결 리스트

이번 블로그에서는 단방향 원형 연결 리스트로 구현하였다

• 일반적인 노드 구조는 동일함
  

• 노드의 갯수를 나타낼 size 변수

• 노드안에 포함된 data값 & next 포인터

• 노드를 가리키는 head 포인터
  

---

🔒 private에 구조와 변수 정의

• 여기서 struct Node는 자기 참조 구조체 라고 한다

  자기 참조 구조체란?
  -> 자기 자신의 자료형을 가리키는 포인터를 멤버로 가지는 구조체를 말한다
  -> 여기서는 노드 구조체 안에 Node * next라고 하는 포인터가 있다
  -> 구조체 노드 안에는 Node형을 가리키는 next포인터를 멤버로 갖고있다

template <typename T>
class CircleLinkedList
{
private:
	int size;

	struct Node
	{
		T data;
		Node* next;
	};

	Node* head;
}

🔒 public 생성자에 값 초기화

• head = nullptr은 노드가 하나도 없다는 것

public:
	// 생성자
	CircleLinkedList()
	{
		size = 0;
		head = nullptr;
	}

✅ PushFront (앞에 데이터 넣기)

• 기본적으로 원형리스트에서 head는 마지막 노드를 가리키고 head의 next는 맨 처음 노드를 가리키기에 앞뒤로 접근하기 편함
  

✔ 노드가 하나도 없을때

• head == nullptr이면 가리키고 있는 곳이 없다는 뜻 (노드가 비어있다)
  
  

• 1. newnode 생성 후 head가 newnode를 가리킴
     
     
• 2. newnode->next는 자기 자신을 가리킴
     

✔ 노드가 여러개일때

• 1. 새 노드를 생성하고 동적할당
     
     
• 2. newnode->next가 head->next를 가리키게 함
     
     
     
• 3. head->next를 newnode로 옮겨줌
     
• 4. size++하여 노드의 크기 수정
     
     
• 5. 여기서 head의 위치는 변하지 않는다 !!

// 앞에 값 넣기
void PushFront(T data)
{
	Node* newnode = new Node;
	newnode->data = data;

	// 노드 하나도 없을때
	if (head == nullptr)
	{
		head = newnode;
		newnode->next = head;
	}
	else
	{
		newnode->next = head->next;
		head->next = newnode;

		// head 위치 그대로 
	}
	size++;
}

---

✅ PushBack (뒤에 데이터 넣기)

• PushFront와 코드는 거의 동일함
  

• 원형 연결 리스트는 앞과 뒤의 구분이 없기 때문에 head값을 기준으로 구분

• head값의 위치를 옮겨주면 된다

// 뒤에 값 넣기
void PushBack(T data)
{
	Node* newnode = new Node;
	newnode->data = data;

	// 노드 하나도 없을때
	if (head == nullptr)
	{
		head = newnode;
		newnode->next = head;
	}
	else
	{
		newnode->next = head->next;
		head->next = newnode;

		// head 위치 옮겨주기
		head = newnode;
	}
	size++;
}

---

✅ PopFront (앞에 데이터 빼기)

• 노드를 지워주기 위한 Node * deleteNode 포인터가 필요함
  

✔ 노드가 하나도 없을때

• 지울 노드가 하나도 없기 때문에 문자 출력
  

✔ 노드가 한개 있을때

• 1. head == head->next는 노드의 next가 자기 자신을 가리키고 있다는 뜻
     
     
     
• 2. deleteNode가 head->next를 가리키고 있으니 head를 nullptr로 옮겨주기
     
• 3. deleteNode가 가리키는 head->next를 delete
     
• 4. size--하여 노드의 크기 수정

// 앞에 값 빼기
void PopFront()
{

	if (head == nullptr)
	{
		cout << "Circle Linked List is Empty" << endl;
	}
	else
	{
		Node* deleteNode = head->next;
		
        // 노드가 한개일때
		if (head == head->next)
		{
			head = nullptr;
		}
		else
		{
			head->next = deleteNode->next;
		}
		delete deleteNode;
		size--;
	}
}

---

✅ PopBack (뒤에 데이터 빼기)

• 노드가 하나도 없을 경우와 노드가 한개뿐인 경우는 PopFront( )와 동일

• 노드가 여러개의 경우

• 1. • deleteNode와 * currentNode 가 head를 가리키게 함
       
• 2. currentNode를 순회를 통해 head의 이전노드 까지 이동 (Size - 1 만큼)
     
• 3. 이제 currentNode는 head의 이전노드가 됨
     
• 4. currentNode -> next 를 head -> next를 가리킴
     

• 기존의 head 위치를 currentNode로 이동
  

• deleteNode가 가리키고 있던 노드를 delete 삭제
  

• 최종적으로 노드가 3개 -> 2개로 변함
  

// 뒤에 값 빼기
void PopBack()
{
	if (head == nullptr)
	{
		cout << "Circle Linked List is Empty" << endl;
	}
	else
	{
		// head의 이전노드 찾기
		Node* currentNode = head;

		Node* deleteNode = head;

		if (head == head->next)
		{
			head = nullptr;
		}
		else
		{
			for (int i = 0; i < size - 1; i++)
			{
				currentNode = currentNode->next;
			}
			currentNode->next = head->next;
			head = currentNode;
		}
		delete deleteNode;
		size--;
	}
}

---

✅ 노드안의 데이터 확인하는 Show( )함수

• 1. currentNode를 만들고 size만큼 순회
     
     
• 2. currentNode가 가리키는 노드의 data 출력
     
     
• 3. currentNode -> next로 이동

void Show()
{
	if (head != nullptr)
	{
		Node* currentNode = head->next;

		for (int i = 0; i < size; i++)
		{
			cout << currentNode->data << " ";
			currentNode = currentNode->next;
		}
	}
}

---

✅ 노드의 갯수를 반환하는 Size( )함수

const int& Size()
{
	return size;
}

---

🔒 노드를 다 해제하는 소멸자

~CircleLinkedList()
{
	while (head != nullptr)
	{
		PopBack();
	}
}

---

📌 메인함수

• 1. 클래스 이름 <자료형> 변수이름;
     
• 2. 변수.함수(매개변수);
• 3. PushBack( )은 뒤에서 부터 값이 들어가기 때문에 출력: 10 20 30
• 4. PushFront( )는 앞에서 부터 값이 들어가기 때문에 출력: 1 5
• 5. PopBack( ) & PopFront( )하면 앞에 값, 뒤에 값 하나씩 삭제

int main()
{
	CircleLinkedList <int> circleLinkedList;

	circleLinkedList.PushBack(10);
	circleLinkedList.PushBack(20);
	circleLinkedList.PushBack(30);

	circleLinkedList.PushFront(5);
	circleLinkedList.PushFront(1);

	circleLinkedList.PopFront();
	circleLinkedList.PopBack();


	circleLinkedList.Show();

	cout << endl << "size : " << circleLinkedList.Size() << endl;

	return 0;
}

출력값 :

---

📌 원형 연결 리스트 장/단점

원형 연결 리스트 장점

• 첫번째 노드만 알면 어떤 위치의 노드든 순차적으로 접근이 가능하다
  *단일 연결리스트의 삽입/삭제 방식과 거의 같지만, 원형 연결 리스트의 처음과 끝에 삽입/삭제가 더 효율적이다

원형 연결 리스트의 단점

• 순차적으로 탐색하는 방법이므로, 배열의 인덱스 접근처럼 임의 접근은 불가능하다

원형 연결 리스트 시간복잡도

삽입/삭제 -> O(1)
-> 포인터가 자기 자신의 다음 노드를 알고있는 상태이기 때문에 삽입/삭제에 상수시간이 걸린다

탐색 -> O(n)
-> 원하는 요소에 접근하려면 노드가 N개 있을때 N번째 노드에 접근하고 싶을 경우, 포인터로 순차적으로 들어가야 하기 때문에 O(N)의 시간이 걸린다

(2024.12.12.목요일)