C++로 연결 리스트가 원형 연결 리스트인지 판별하는 방법

개요

이 글에서는 C++에서 주어진 연결 리스트(Linked List)가 원형 연결 리스트(Circular Linked List)인지 판별하는 방법을 알아봅니다.

판별 원리는 간단합니다. 먼저 시작(헤드) 노드를 별도의 변수에 저장해 둔 뒤 리스트를 순회합니다. 순회 중 어떤 노드의 next 포인터가 NULL을 가리키면 마지막 노드가 존재하는 것이므로 일반 연결 리스트입니다. 반대로 순회하다가 처음에 저장해 둔 시작 노드와 동일한 노드를 다시 만나게 되면, 리스트의 끝이 시작점으로 되돌아오는 것이므로 원형 연결 리스트라고 판단할 수 있습니다.

알고리즘 동작 순서

1. 시작 노드가 NULL이면 빈 리스트이므로 true를 반환합니다.
2. 임시 포인터 node를 start->next로 초기화합니다.
3. node가 NULL이 아니고 시작 노드와 같지 않은 동안 계속 다음 노드로 이동합니다.
4. 반복이 끝난 후 node == start라면 원형 리스트이고, 그렇지 않다면 일반 리스트입니다.

이 방법의 시간 복잡도는 리스트를 한 번만 순회하므로 O(n)이며, 추가 메모리는 포인터 하나만 사용하므로 공간 복잡도는 O(1)입니다.

예제 코드

#include <iostream>
using namespace std;
class Node{
   public:
   int data;
   Node *next;
};
Node* getNode(int data){
   Node *newNode = new Node;
   newNode->data = data;
   newNode->next = NULL;
   return newNode;
}
bool isCircularList(Node *start){
   if(start == NULL)
      return true;
   Node *node = start->next;
   while(node != NULL && node != start){
      node = node->next;
   }
   if(node == start)
      return true;
      return false;
}
int main() {
   Node *start = getNode(10);
   start->next = getNode(20);
   start->next->next = getNode(30);
   start->next->next->next = getNode(40);
   start->next->next->next->next = getNode(50);
   start->next->next->next->next->next = start;
   if (isCircularList(start))
      cout << "The list is circular list";
   else
      cout << "The list is not circular list";
}

실행 결과

The list is circular list

코드 설명

위 예제에서는 10부터 50까지 다섯 개의 노드로 구성된 연결 리스트를 만들고, 마지막 노드(50)의 next가 첫 번째 노드(start)를 가리키도록 설정하여 원형 구조를 만들었습니다. 따라서 isCircularList() 함수는 순회 중 다시 시작 노드에 도달하게 되어 true를 반환하고, "원형 리스트"라는 결과가 출력됩니다.

만약 마지막 줄에서 next를 start 대신 NULL로 설정했다면, 순회 중 NULL을 만나 반복문이 종료되어 "원형 리스트가 아님"이라는 결과가 출력됩니다.