이중연결리스트(Doubly Linked Lists) - C++

개요

단일 연결 리스트는 한쪽 방향으로 연결된 노드로 구성됩니다. 따라서 액세스 및 순회는 첫 번째 노드인 Head에서 시작하여 한번에 한 노드씩 확인하며 진행해야 합니다. 만약 역순으로 액세스 및 순회를 하고자 한다면 이를 효율적으로 할 수는 없을 것입니다. 순회를 위하여 매번 Head에서 시작하여 이전 순회보다 한 노드씩 앞에서 중단하는 방식으로 여러 차례 반복적으로 순회를 수행해야 하기 때문입니다.

따라서 만약 역순으로 순회를 해야 하는 경우가 필요하다면 이번 포스트에서 소개하는 이중 연결리스트(Doubly Linked List)를 도입하는 것이 좋습니다.

이중 연결리스트 예시

구현 (C++)

이중 연결 리스트

각 노드는 3가지 멤버변수를 가지고 있습니다. 두 가지는 각각 이전 노드와 다음 노드를 가리키는 링크 값(포인터)이며, 하나는 노드의 데이터입니다. 시작 노드의 이전 노드와 마지막 노드의 다음 노드를 가리키는 링크 값은 일반적으로 센티널 노드(Sentinel Node) 또는 null을 가르켜 종료를 표시합니다.

#include <string>
#include <iostream>

using namespace std;

class Node {
    string strData;
    Node* pStPrev;
    Node* pstNext;
    friend class DLinkedList;
};

class DLinkedList {
    public:
        DLinkedList();  // create empty list
        ~DLinkedList();
        bool isEmpty() const;
        const string& getFront() const;
        const string& getBack() const;
        void addFront(const string& e);
        void addBack(const string& e);
        void removeFront();
        void removeBack();
        void TraverseForward();
        void TraverseBackward();
    private:
        Node* header;
        Node* trailer;
    protected: // local utilities
        void add(Node* v, const string& e);
        void remove(Node* v);
};

DLinkedList::DLinkedList() {
    header = new Node;
    trailer = new Node;

    // Header and Trailer are sentinel Nodes.
    // No data is included at those nodes.
    header->pstNext = trailer;
    trailer->pStPrev = header;
}

DLinkedList::~DLinkedList() {
    while(!isEmpty()) removeFront();
    delete header;
    delete trailer;
}

bool DLinkedList::isEmpty() const {
    if (header->pstNext == trailer);
}

const string& DLinkedList::getFront() const {
    return header->pstNext->strData;
}

const string& DLinkedList::getBack() const {
    return trailer->pStPrev->strData;
}

삽입 및 삭제

Header 및 Trailer를 Sentinel Node로 사용하여 구현을 쉽게 할 수 있습니다. 해당 노드에는 Data 가 저장되지 않으며 실제 Node는 Header의 다음에서 시작하여 Trailer의 이전에서 종료되도록 하여 삽입 및 삭제를 일반화할 수 있습니다.

void DLinkedList::addFront(const string& e) {
    add(header, e);
}

void DLinkedList::addBack(const string& e) {
    add(trailer->pStPrev, e);
}


// Insert new Node after v
void DLinkedList::add(Node* v, const string& e) {
    Node* u = new Node;
    u->strData = e;
    u->pstNext = v->pstNext;
    u->pStPrev = v;

    v->pstNext->pStPrev = u;
    v->pstNext = u;
}


void DLinkedList::removeFront() {
    remove(header->pstNext);
}

void DLinkedList::removeBack() {
    remove(trailer->pStPrev);
}

void DLinkedList::remove(Node* v) {
    Node* u = v->pStPrev;
    Node* w = v->pstNext;
    u->pstNext = w;
    w->pStPrev = u;
    delete v;
}

void DLinkedList::TraverseForward() {
    Node* v = header->pstNext;
    while(v->pstNext != NULL) {
        cout << v->strData << " ";
        v = v->pstNext;
    }
}

void DLinkedList::TraverseBackward() {
    Node* v = trailer->pStPrev;
    while(v->pStPrev != NULL) {
        cout << v->strData << " ";
        v = v->pStPrev;
    }
}

int main (void) {
    DLinkedList* DL = new DLinkedList();

    DL->addFront("3");
    DL->addFront("5");
    DL->addFront("8");
    DL->addFront("10");

    // 3 -> 5 -> 8 -> 10
    DL->TraverseBackward();

    cout << endl;

    // 10 -> 8 -> 5 -> 3
    DL->TraverseForward();

    cout << endl;

    DL->removeBack();
    DL->removeBack();

    // 10 -> 8
    DL->TraverseForward();
    cout << endl;    

    return EXIT_SUCCESS;
}