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

---

 

원형 이중 연결 리스트(Circular Doubly Linked List)는 각 노드가 두 개의 포인터를 가지고,

하나는 다음 노드를 가리키고 다른 하나는 이전 노드를 가리킵니다.

이 리스트는 마지막 노드가 첫 번째 노드를 가리키고,

첫 번째 노드가 마지막 노드를 가리키는 구조를 가지고 있어 리스트의 처음과 끝을 쉽게 순환할 수 있습니다.

 

---

 

#include <iostream>

class Node {
public:
    int data;
    Node* next;
    Node* prev;

    Node(int value) : data(value), next(nullptr), prev(nullptr) {}
};

class CircularDoublyLinkedList {
private:
    Node* head;

public:
    CircularDoublyLinkedList() : head(nullptr) {}

    // 리스트가 비어있는지 확인
    bool isEmpty() const {
        return head == nullptr;
    }

    // 리스트에 노드 추가 (맨 끝에)
    void append(int value) {
        Node* newNode = new Node(value);
        if (isEmpty()) {
            head = newNode;
            head->next = head;
            head->prev = head;
        } else {
            Node* tail = head->prev;
            tail->next = newNode;
            newNode->prev = tail;
            newNode->next = head;
            head->prev = newNode;
        }
    }

    // 리스트의 모든 노드를 순회하며 출력
    void display() const {
        if (isEmpty()) {
            std::cout << "리스트가 비어 있습니다." << std::endl;
            return;
        }
        Node* current = head;
        do {
            std::cout << current->data << " ";
            current = current->next;
        } while (current != head);
        std::cout << std::endl;
    }

    // 노드 삭제 (주어진 값)
    void remove(int value) {
        if (isEmpty()) return;
        Node* current = head;
        do {
            if (current->data == value) {
                if (current->next == current) {
                    head = nullptr;
                } else {
                    current->prev->next = current->next;
                    current->next->prev = current->prev;
                    if (current == head) {
                        head = current->next;
                    }
                }
                delete current;
                return;
            }
            current = current->next;
        } while (current != head);
    }

    ~CircularDoublyLinkedList() {
        if (!isEmpty()) {
            Node* current = head;
            Node* nextNode;
            do {
                nextNode = current->next;
                delete current;
                current = nextNode;
            } while (current != head);
        }
    }
};

int main() {
    CircularDoublyLinkedList list;

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

    std::cout << "리스트 입력 10, 20, 30, 40: ";
    list.display();

    list.remove(20);
    std::cout << "데이터 삭제 20: ";
    list.display();

    list.remove(10);
    std::cout << "데이터 삭제 10: ";
    list.display();

    return 0;
}

 

• 'isEmpty' 함수
  리스트가 비어있는지 확인하는 함수입니다.
  헤드가 nullptr이면 리스트는 비어있는 것입니다.
  
  
• 'append' 함수
  리스트의 끝에 새로운 노드를 추가합니다.
  리스트가 비어있을 경우, 새 노드는 헤드가 되고 자기 자신을 가리키도록 합니다.
  그렇지 않으면, 현재의 마지막 노드와 헤드를 업데이트합니다.
  
  
• 'display' 함수
  리스트의 모든 노드를 순회하며 데이터를 출력합니다.
  리스트가 비어있으면 해당 메시지를 출력합니다.
  
  
• 'remove' 함수
  주어진 값을 가지는 노드를 리스트에서 제거합니다.
  리스트가 비어있는지 확인하고,
  각 노드를 순회하며 값을 찾으면 해당 노드를 삭제하고 링크를 업데이트합니다.
  
  
• 소멸자 ('~CircularDoublyLinkedList')
  리스트가 삭제될 때 모든 노드를 메모리에서 해제합니다.
  
  

 

제 글이 도움이 되셨다면 댓글 & 공감 부탁드려요 😀