[기초] C++ Linked List : 원형 연결 리스트

---

 

원형 연결 리스트는 마지막 노드가 첫 번째 노드를 가리키도록 연결된 연결 리스트입니다.

이는 리스트의 끝에서 다시 처음으로 순환할 수 있게 하여 특정 유형의 문제에 유용합니다.

원형 연결 리스트는 단일 연결 리스트와 달리,

끝이 명확하지 않으므로 반복 작업에서 유용할 수 있습니다.

 

---

 

#include <iostream>

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

class CircularLinkedList {
private:
    Node* head;
public:
    CircularLinkedList() : head(nullptr) {}

    // 노드 추가
    void append(int data) {
        Node* newNode = new Node(data);
        if (!head) {
            head = newNode;
            head->next = head;
        } else {
            Node* temp = head;
            while (temp->next != head) {
                temp = temp->next;
            }
            temp->next = newNode;
            newNode->next = head;
        }
    }

    // 노드 출력
    void printList() {
        if (!head) {
            std::cout << "리스트가 비어 있습니다.\n";
            return;
        }
        Node* temp = head;
        do {
            std::cout << temp->data << " ";
            temp = temp->next;
        } while (temp != head);
        std::cout << std::endl;
    }

    // 소멸자
    ~CircularLinkedList() {
        if (!head) return;
        Node* current = head;
        Node* nextNode;
        do {
            nextNode = current->next;
            delete current;
            current = nextNode;
        } while (current != head);
    }
};

int main() {
    CircularLinkedList cll;

    cll.append(10);
    cll.append(20);
    cll.append(30);
    cll.append(40);

    cll.printList(); // 출력: 10 20 30 40

    return 0;
}

 

코드 설명

 

• 노드 추가
  'append' 함수는 리스트의 끝에 새로운 노드를 추가합니다.
  첫 번째 노드는 자기 자신을 가리키도록 설정됩니다 ('head->next = head')
  그 이후 추가되는 노드는 리스트의 끝에 삽입되고,
  새로운 노드의 'next' 포인터가 'head'를 가리키도록 합니다.
  
  
• 노드 출력
  'printList' 함수는 리스트의 모든 노드를 순환하며 출력합니다.
  리스트가 비어 있는 경우, "리스트가 비어 있습니다."라는 메시지를 출력합니다.
  비어 있지 않은 경우, 'head'부터 시작하여 순환하며 각 노드의 데이터를 출력합니다.
  
  
• 소멸자
  소멸자 '~CircularLinkedList'는 리스트의 모든 노드를 해제하여 메모리 누수를 방지합니다.
  순환 구조로 인해 모든 노드를 순환하면서 하나씩 삭제합니다.
  
  

 

주요 특징

 

• 순환 구조
  마지막 노드의 `next` 포인터가 첫 번째 노드를 가리킵니다.
  
  
• 항상 연결됨
  리스트의 어떤 지점에서도 리스트의 모든 노드를 순환할 수 있습니다.
  
  
• 시작 지점 없음
  어떤 노드도 리스트의 시작점이 될 수 있습니다.