Circular doubly linked list [c++]

---

Circular doubly linked list의 개념

Circular doubly linked list의 Circular singly linked list와의 가장 큰 차이점은 첫 번째 노드가 자신의 이전 노드로 마지막 노드를 가리킨다는 것입니다. 헤드과 테일을 연결했을 때의 장점은 head를 알면 tail을 알 수 있고, tail을 알면, head를 알 수 있다는 점입니다. 예를 들어서 이중 연결 리스트를 환형으로 구현하면 head의 이전 노드가 tail이 되고, tail의 이전 노드가 head가 됩니다. 이 경우 tail에 접근하는 비용이 거의 없는 것이나 다름없을 정도로 작아져 appendNode() 함수의 성능을 획기적으로 개선할 수 있고, tail부터 노드를 찾아나가는 노드 탐색 함수를 구현할 수도 있습니다.

---

c++로 구현한 Circular doubly linked list

---

#include <iostream>
using namespace std;
template <typename T>
struct Node{
        T data;
        struct Node* next;
        struct Node* pre;
};
template <typename T>
class CircularDoublyLinkedList{
        private:
                Node<T>* head_;
        public:
                CircularDoublyLinkedList();
                ~CircularDoublyLinkedList();

                void printAll();
                Node<T>* createNode(T newData);
                void destroyNode(Node<T>* node);
                void appendNode(Node<T>* newNode);
                void insertNode(Node<T>* current, Node<T>* newNode);
                void insertNewHead(Node<T>* newHead);
                void removeNode(Node<T>* Remove);
                void removeHead();
                void removeTail();
                int getSize();
                Node<T>* getNodeAt(int location);
};
template <typename T>
CircularDoublyLinkedList<T>::CircularDoublyLinkedList():head_(nullptr){

}
template <typename T>
CircularDoublyLinkedList<T>::~CircularDoublyLinkedList(){
        Node<T>* current = head_;

        while (current != nullptr){
                Node<T>* temp = current;
                current = current->next;
                destroyNode(temp);
        }
}
template <typename T>
void CircularDoublyLinkedList<T>::printAll(){
        Node<T>* current = head_;

        cout << "start -> " << current->data << " -> ";
        while (current->next != head_){
                current = current->next;
                cout << current->data << " -> ";
        }
        cout << "end" << endl;
}
template <typename T>
Node<T>* CircularDoublyLinkedList<T>::createNode(T newData){
        Node<T>* newNode = new Node<T>;

        newNode->data = newData;
        newNode->pre = nullptr;
        newNode->next = nullptr;

        return newNode;
}
template <typename T>
void CircularDoublyLinkedList<T>::destroyNode(Node<T>* node){
        node->next = nullptr;
        node->pre = nullptr;

        delete node;
}
template <typename T>
void CircularDoublyLinkedList<T>::appendNode(Node<T>* newNode){
        if (head_ == nullptr){
                head_ = newNode;
                head_->next = newNode;
                head_->pre = newNode;
        }
        else {
                newNode->next = head_->pre->next;
                newNode->pre = head_->pre;
                head_->pre = newNode;
                newNode->pre->next = newNode;
        }
}
template <typename T>
void CircularDoublyLinkedList<T>::insertNode(Node<T>* current, Node<T>* newNode){
        newNode->next = current->next;
        newNode->pre = current->next->pre;
        current->next = newNode;
        newNode->next->pre = newNode;
}
template <typename T>
void CircularDoublyLinkedList<T>::insertNewHead(Node<T>* newHead){
        appendNode(newHead);
        head_ = newHead;
}
template <typename T>
void CircularDoublyLinkedList<T>::removeNode(Node<T>* Remove){
        if (head_ == Remove){
                removeHead();
        }
        else {
                Remove->next->pre = Remove->pre;
                Remove->pre->next = Remove->next;

                destroyNode(Remove);
        }
}
template <typename T>
void CircularDoublyLinkedList<T>::removeHead(){
        head_->pre->next = head_->next;
        head_->next->pre = head_->pre;

        Node<T>* temp = head_;
        head_ = head_->next;

        destroyNode(temp);
}
template <typename T>
void CircularDoublyLinkedList<T>::removeTail(){
        if (head_ == head_->pre){
                destroyNode(head_);
        }
        else {
                Node<T>* tail = head_->pre;

                tail->next->pre = tail->pre;
                tail->pre->next = tail->next;

                destroyNode(tail);
        }
}
template <typename T>
int CircularDoublyLinkedList<T>::getSize(){
        int count = 1;
        Node<T>* current = head_;

        while (current->next != head_){
                current = current->next;
                count++;
        }

        return count;
}
template <typename T>
Node<T>* CircularDoublyLinkedList<T>::getNodeAt(int location){
        Node<T>* current = head_;

        while ((--location) > 0){
                current = current->next;
        }

        return current;
}

int main(){
        CircularDoublyLinkedList<int>* list = new CircularDoublyLinkedList<int>();
        Node<int>* temp = new Node<int>;
        for (int i=0;i<3;i++){
                temp = list->createNode(i+1);
                list->appendNode(temp);
        }

        list->printAll();

        for (int i=0;i<3;i++){
                temp = list->createNode(i+4);
                list->insertNewHead(temp);
        }

        list->printAll();

        list->insertNode(list->getNodeAt(3), list->createNode(7));//세 번째 노드 뒤에 삽입
        list->printAll();

        list->removeHead();
        list->printAll();

        list->removeTail();
        list->printAll();

        list->removeNode(list->getNodeAt(3));
        list->printAll();

        return 0;
}

출력
start -> 1 -> 2 -> 3 -> end
start -> 6 -> 5 -> 4 -> 1 -> 2 -> 3 -> end
start -> 6 -> 5 -> 4 -> 7 -> 1 -> 2 -> 3 -> end
start -> 5 -> 4 -> 7 -> 1 -> 2 -> 3 -> end
start -> 5 -> 4 -> 7 -> 1 -> 2 -> end
start -> 5 -> 4 -> 1 -> 2 -> end