Doubly linked list [c++]

Doubly linked list의 개념

---

doubly linked list는 singly linked list의 탐색 기능을 개선한 자료구조입니다. singly linked list는 특정 노드를 찾기 위해서 head에서 tail방향으로만 탐색할 수 있는 반면, doubly linked list에서는 양방향 탐색이 가능합니다.

Doubly linked list의 노드는 데이터를 보관하는 필드, 다음 노드를 가리키는 포인터, 추가적으로 이전 노드를 가리키는 포인터를 갖고 있습니다.

이 노드를 엮으면 다음 그림과 같은 모습의 doubly linked list가 됩니다.

---

c++로 구현한 Doubly linked list

---

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

                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>
DoublyLinkedList<T>::DoublyLinkedList():head_(nullptr), tail_(nullptr){

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

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

        cout << "start -> ";
        while (current != '\0'){
                cout << current->data << " -> ";
                current = current->next;
        }
        cout << " end" << endl;
}
template <typename T>
Node<T>* DoublyLinkedList<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 DoublyLinkedList<T>::destroyNode(Node<T>* node){
        node->pre = nullptr;
        node->next = nullptr;

        delete node;
}
template <typename T>
void DoublyLinkedList<T>::appendNode(Node<T>* newNode){
        if (head_ == nullptr){
                head_ = newNode;
        }
        else {
                tail_->next = newNode;
                newNode->pre = tail_;
        }

        tail_ = newNode;
}
template <typename T>
void DoublyLinkedList<T>::insertNode(Node<T>* current, Node<T>* newNode){
        if (current == tail_){
                appendNode(tail_, newNode);
        }
        else {
                newNode->next = current->next;
                current->next = newNode;

                newNode->pre = current;
                newNode->next->pre = newNode;
        }
}
template <typename T>
void DoublyLinkedList<T>::insertNewHead(Node<T>* newHead){
        if (head_ == nullptr){
                tail_ = newHead;
        }
        else {
                head_->pre = newHead;
                newHead->next = head_;
        }
        head_ = newHead;
}
template <typename T>
void DoublyLinkedList<T>::removeNode(Node<T>* Remove){
        if (head_ == Remove){
                removeHead();
        }
        else if (tail_ == Remove){
                removeTail();
        }
        else {
                Node<T>* temp = Remove;

                Remove->pre->next = temp->next;
                Remove->next->pre = temp->pre;

                destroyNode(temp);
        }
}
template <typename T>
void DoublyLinkedList<T>::removeHead(){
        if (head_ == tail_){
                head_ = nullptr;
                tail_ = nullptr;
        }
        else {
                Node<T>* temp = head_;

                head_ = head_->next;
                head_->pre = nullptr;

                destroyNode(temp);
        }
}
template <typename T>
void DoublyLinkedList<T>::removeTail(){
        if (head_ == tail_){
                head_ = nullptr;
                tail_ = nullptr;
        }
        else {
                Node<T>* temp = tail_;

                tail_ = tail_->pre;
                tail_->next = nullptr;

                destroyNode(temp);
        }
}
template <typename T>
int DoublyLinkedList<T>::getSize(){
        Node<T>* current = head_;
        int count = 0;

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

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

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

        return current;
}
int main(){
        DoublyLinkedList<int>* list = new DoublyLinkedList<int>();

        for (int i=0;i<2;i++){
                Node<int>* newNode = list->createNode(i+1);
                list->appendNode(newNode);
        }

        for (int i=0;i<2;i++){
                Node<int>* newNode = list->createNode(i+3);
                list->insertNewHead(newNode);
        }
        list->printAll();

        Node<int>* temp = list->getNodeAt(4);
        list->removeNode(temp);

        list->printAll();

        temp = list->getNodeAt(2);
        list->removeNode(temp);

        list->printAll();

        return 0;
}

출력
start -> 4 -> 3 -> 1 -> 2 -> end
start -> 4 -> 3 -> 1 -> end
start -> 4 -> 1 -> end

---