이중 원형 연결 리스트의 노드 클래스 설계

이중 연결 리스트의 핵심은 각 노드가 이전 노드와 다음 노드를 모두 가리키는 포인터를 가진다는 점입니다. 템플릿을 활용하여 다양한 데이터 타입을 지원하도록 구현합니다.

template<typename T>
class DNode {
public:
    T data;
    DNode* next;
    DNode* prev;
    
    DNode() : data(T()), next(nullptr), prev(nullptr) {}
    explicit DNode(const T& value) : data(value), next(nullptr), prev(nullptr) {}
};

리스트 클래스 구조 정의

리스트 클래스는 헤드 노드와 크기 정보를 관리합니다. 헤드 노드는 더미 노드(dummy node)로 사용하여 구현을 단순화합니다.

template<typename T>
class CircularDoublyLinkedList {
private:
    DNode<T>* head;
    int size;
    
public:
    CircularDoublyLinkedList();
    ~CircularDoublyLinkedList();
    
    bool isEmpty() const;
    int getSize() const;
    void insert(int position, const T& value);
    void remove(int position);
    void update(int position, const T& value);
    T get(int position) const;
    void display(int count) const;
};

생성자와 초기화

초기 상태에서는 헤드 노드의 next와 prev가 자기 자신을 가리키도록 설정하여 빈 원형 구조를 만듭니다.

template<typename T>
CircularDoublyLinkedList<T>::CircularDoublyLinkedList() 
    : head(new DNode<T>()), size(0) {
    head->next = head;
    head->prev = head;
}

노드 삽입 구현

지정된 위치에 새 노드를 삽입합니다. 위치가 유효하지 않으면 예외를 발생시킵니다.

template<typename T>
void CircularDoublyLinkedList<T>::insert(int position, const T& value) {
    if (position < 0 || position > size) {
        throw std::out_of_range("삽입 위치가 범위를 벗어났습니다.");
    }
    
    DNode<T>* newNode = new DNode<T>(value);
    DNode<T>* current = head;
    
    // 삽입 위치까지 이동
    for (int i = 0; i < position; ++i) {
        current = current->next;
    }
    
    // 4개의 포인터 연결
    newNode->next = current->next;
    newNode->prev = current;
    current->next->prev = newNode;
    current->next = newNode;
    
    ++size;
}

노드 삭제와 메모리 해제

특정 위치의 노드를 제거하고 메모리를 해제합니다. 삭제 후에도 원형 연결을 유지해야 합니다.

template<typename T>
void CircularDoublyLinkedList<T>::remove(int position) {
    if (position < 0 || position >= size) {
        throw std::out_of_range("삭제 위치가 범위를 벗어났습니다.");
    }
    
    DNode<T>* target = head->next;
    
    // 대상 노드까지 이동
    for (int i = 0; i < position; ++i) {
        target = target->next;
    }
    
    // 포인터 재연결
    target->prev->next = target->next;
    target->next->prev = target->prev;
    
    delete target;
    --size;
}

데이터 조회 및 수정

조회와 수정은 모두 위치 기반으로 동작하며, 내부적으로 순회하여 접근합니다.

template<typename T>
T CircularDoublyLinkedList<T>::get(int position) const {
    if (position < 0 || position >= size) {
        throw std::out_of_range("조회 위치가 범위를 벗어났습니다.");
    }
    
    DNode<T>* current = head->next;
    for (int i = 0; i < position; ++i) {
        current = current->next;
    }
    return current->data;
}

template<typename T>
void CircularDoublyLinkedList<T>::update(int position, const T& value) {
    if (position < 0 || position >= size) {
        throw std::out_of_range("수정 위치가 범위를 벗어났습니다.");
    }
    
    DNode<T>* current = head->next;
    for (int i = 0; i < position; ++i) {
        current = current->next;
    }
    current->data = value;
}

리스트 출력

원형 구조이므로 count 매개변수로 출력할 노드 개수를 지정합니다.

template<typename T>
void CircularDoublyLinkedList<T>::display(int count) const {
    if (isEmpty()) {
        std::cout << "리스트가 비어 있습니다." << std::endl;
        return;
    }
    
    DNode<T>* current = head->next;
    for (int i = 0; i < count && current != head; ++i) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

소멸자 구현

모든 동적 할당된 노드를 안전하게 해제합니다.

template<typename T>
CircularDoublyLinkedList<T>::~CircularDoublyLinkedList() {
    if (isEmpty()) {
        delete head;
        return;
    }
    
    DNode<T>* current = head->next;
    while (current != head) {
        DNode<T>* next = current->next;
        delete current;
        current = next;
    }
    delete head;
}

사용 예제

#include <iostream>
#include "CircularDoublyLinkedList.h"

int main() {
    CircularDoublyLinkedList<int> intList;
    
    // 정수형 리스트 테스트
    intList.insert(0, 10);
    intList.insert(1, 20);
    intList.insert(1, 15);  // 위치 1에 15 삽입
    
    intList.display(5);  // 출력: 10 15 20
    
    intList.remove(1);
    intList.display(3);  // 출력: 10 20
    
    intList.update(0, 25);
    std::cout << "위치 0의 값: " << intList.get(0) << std::endl;  // 출력: 25
    
    // 부동소수점 리스트 테스트
    CircularDoublyLinkedList<double> doubleList;
    doubleList.insert(0, 3.14);
    doubleList.insert(1, 2.718);
    doubleList.display(3);  // 출력: 3.14 2.718
    
    return 0;
}

이 구현의 특징은 템플릿을 사용하여 int, double, 사용자 정의 클래스 등 다양한 타입을 지원한다는 점입니다. 원형 구조 덕분에 head에서 next를 따라가면 리스트의 처음으로 다시 돌아오며, 이는 순환 처리가 필요한 상황에 유용합니다. 실제 프로젝트에서는 STL의 std::list나 std::forward_list를 사용하는 것이 더 효율적일 수 있지만, 자료구조 학습 목적으로는 직접 구현해보는 것이 도움이 됩니다.