더블 링크드 리스트(Doubly Linked List)

양방향으로 탐색하자!

이번에는 단순 연결 리스트(Singly Linked List: SLL)가 아닌, 이중 연결 리스트(Doubly Linked List: DLL)입니다. 단순 연결 리스트는 헤드부터 시작해서 테일까지 탐색해야 하는 단방향 탐색이었지만, 이중 연결 리스트는 헤드에서 테일, 테일에서 헤드 방향으로 탐색이 가능한 양방향 탐색입니다. 단순 연결 리스트의 노드는 다음 노드를 가리키는 포인터만 있는 반면에, 이중 연결 리스트의 노드는 다음 노드를 가리키는 포인터뿐만 아니라 이전 노드를 가리키는 포인터가 존재합니다.

위의 그림에서 노드를 보시면 이전 노드를 가리키는 포인터(PrevLink)와, 데이터(Data), 그리고 다음 노드를 가리키는 포인터(NextLink)로 구성되어 있습니다. (이미 다 아시겠지만, 제일 앞에 있는 노드가 헤드, 마지막에 있는 노드가 테일입니다.) 이중 연결 리스트를 구현하기 전에, 이중 연결 리스트의 노드는 어떻게 생성하는지 살펴봅시다.

class Node
{
public:
    string data; // 데이터 필드
    Node* NextLink; // 다음 노드를 가리키는 포인터
    Node* PrevLink; // 이전 노드를 가리키는 포인터
};

Node 클래스의 멤버 변수가 하나 더 늘어났죠? 단순 연결 리스트와 비교하면 이전 노드를 가리키는 포인터가 새로 생겨났습니다. 곧바로 단순 연결 리스트에서 이중 연결 리스트로 넘어오면서 리스트 클래스가 어떻게 바뀌었는지, 추가와 소멸, 출력 함수는 어떻게 바뀌었는지 같이 살펴보도록 합시다.

class DLL
{
public:
    Node* Head; // 리스트의 머리 부분, 처음 부분
    Node* Tail; // 리스트의 꼬리 부분, 마지막 부분
};

단순 연결 리스트에선 헤드(Head)만 있던 게, 이번에는 테일(Tail)이 추가되었습니다. 역시, DLL 클래스의 생성자에서 Head와 Tail를 NULL로 초기화해주어야 합니다. 추가 함수를 살펴봅시다.

void appendNode(string data)
{
    Node* newNode = new Node(); // 새로운 노드를 생성한다.
    newNode->data = data; // 이 노드의 데이터에 집어넣으려는 데이터로 초기화 시킨다.
    newNode->NextLink = NULL; // 다음 노드를 이어주는 링크를 NULL로 초기화 시킨다.
    newNode->PrevLink = NULL; // 이전 노드를 이어주는 링크를 NULL로 초기화 시킨다.

    if (Head != NULL) { // 노드를 처음 추가하는 것이 아니라면
        Tail->NextLink = newNode; // 꼬리 노드의 다음 노드를 새로 추가된 노드로 지정한다 
        newNode->PrevLink = Tail; // 새로 추가된 노드의 이전 노드를 꼬리 노드로 지정한다
        Tail = newNode; // 꼬리 노드를 새로 추가된 노드로 지정한다
    }
    else { // 노드를 처음 추가하는 것이라면
        Head = Tail = newNode; // 새로 추가한 노드를 헤드로 지정함과 동시에 테일로도 지정한다
    }
}

이중 연결 리스트의 appendNode 함수입니다. 단순 연결 리스트와는 달리 이전 노드를 가리키는 포인터도 NULL로 초기화합니다. 11행을 보시면, 꼬리 노드의 다음에 오는 노드를 추가되는 노드로 지정합니다. 그러고 나서 12행에선, 새로 추가된 노드의 이전에 오는 노드를 현재 꼬리 노드로 지정합니다. 그리고 13행에선, 새로 추가된 노드가 이제부턴 제일 마지막에 위치하는 노드이므로 꼬리 노드를 새로 추가된 노드로 지정합니다. 이번엔 삭제 노드를 살펴보는데, 이전 링크와 다음 링크를 함께 다루다 보니 단순 연결 리스트에 비해 삭제 과정이 복잡해졌습니다.

단순 연결 리스트의 삭제 함수는 두개의 포인터를 다루는 반면에, 이중 연결 리스트의 삭제 함수는 네 개의 포인터를 다룹니다. 삭제가 어떻게 이루어지는지 함수를 살펴보도록 합시다.

void deleteNode(string data)
{
    Node* pNode = Head; // 임시 포인터에 헤드의 주소 값으로 초기화 한다
    if (pNode == NULL) return; // 한번도 추가하지 않았다면 그냥 빠져나온다
    else { // 노드가 하나 이상 존재한다면
        Node* prevNode; // 이전 노드를 담을 Node 클래스 포인터
        Node* nextNode; // 다음 노드를 담을 Node 클래스 포인터

        do {
            // data와 pNode->data와 비교하여 일치하면 반복문을 빠져 나온다
            if (data.compare(pNode->data) == 0) break;
            pNode = pNode->NextLink; // 임시 노드에 다음 노드의 주소값을 대입한다.

        } while (pNode != NULL); // 임시 포인터의 주소값이 NULL이 될때까지 반복 
        prevNode = pNode->PrevLink; // 삭제하려는 노드의 이전 노드를 가리킨다
        nextNode = pNode->NextLink; // 삭제하려는 노드의 다음 노드를 가리킨다

        // 삭제하려는 노드의 이전 노드가 없으면 헤드(Head) 노드이므로 삭제하려는 노드의 다음 노드를 헤드 노드로 지정
        if (prevNode == NULL) Head = nextNode;
        // 위의 경우가 아니라면 삭제하려는 노드의 이전 노드가 삭제하려는 노드의 다음 노드를 가리키게 한다
        else prevNode->NextLink = nextNode;
        // 삭제하려는 노드의 다음 노드가 없으면 테일(Tail) 노드이므로 삭제하려는 노드의 이전 노드를 테일 노드로 지정
        if (nextNode == NULL) Tail = prevNode;
        // 위의 경우가 아니라면 삭제하려는 노드의 다음 노드가 삭제하려는 노드의 이전 노드를 가리키게 한다
        else nextNode->PrevLink = prevNode;
        delete pNode; // pNode를 메모리 공간에서 해제시킨다
    }
}

추가된 부분인 17행부터 설명을 진행하도록 하겠습니다. 17, 18행에선 삭제하려는 노드의 이전 노드와 다음 노드를 먼저 구합니다. 그러고 나서 21행에서, 삭제하려는 노드의 이전에 위치하는 노드가 NULL, 즉 비어있을 경우에 이 노드는 헤드(Head, 머리) 노드 이므로 기존의 헤드 노드가 삭제되면 헤드가 비어있기 때문에 삭제하려는 노드의 다음 노드를 가리키게 합니다. 만약 이전 노드가 존재한다면, 이전 노드가 가리키는 다음 노드를 삭제하려는 노드의 다음 노드를 가리키게 합니다. 밑의 테일 노드도 같습니다. 이번에는 출력 함수를 살펴보도록 합시다.

void printNode() {
    Node* tempPoint = Head; // 임시 포인터를 생성하고 이 포인터에 헤드의 주소 값을 대입
    
    // 노드가 하나도 존재하지 않으면 함수를 빠져나옴    
    if (tempPoint == NULL) { cout << "리스트가 비어 있습니다." << endl; return; }
    // 노드가 하나만 존재할 경우
    if (tempPoint->NextLink == NULL) { cout << tempPoint->data << "->" << "NULL" << endl; }
    // 노드가 하나가 아닌 하나 이상 존재할 경우
    else {
        while (tempPoint != NULL) // 임시 포인터가 NULL이 될때까지 반복
        {
            cout << tempPoint->data << "<->"; // 임시 포인터의 데이터를 출력한다
            tempPoint = tempPoint->NextLink; // 임시 포인터의 NextlINK의 값을 대입한다
        }
        cout << "NULL" << endl; // 마지막에는 노드가 없음을 나타내기 위해 NULL 표시/개행
    }
}

출력 함수는 살펴보니 바뀐게 없는 것 같죠? 네, 없습니다. 헤드에서부터 테일 방향으로 순서대로 출력하는 함수죠. 아래는 이중 연결 리스트 예제의 전체 소스입니다.

예제소스

#include <iostream>
#include <string>

using namespace std;
class Node
{
public:
    string data; // 데이터 필드
    Node* NextLink; // 다음 노드를 가리키는 포인터
    Node* PrevLink; // 이전 노드를 가리키는 포인터
};

class DLL
{
public:
    Node* Head; // 리스트의 머리 부분, 처음 부분
    Node* Tail; // 리스트의 꼬리 부분, 마지막 부분
    
    DLL()
    {
        Head = NULL; // 헤드(Head)의 초기화
        Tail = NULL; // 테일(Tail)의 초기화
    }

    void appendNode(string data)
    {
        Node* newNode = new Node(); // 새로운 노드를 생성한다.
        newNode->data = data; // 이 노드의 데이터에 집어넣으려는 데이터로 초기화 시킨다.
        newNode->NextLink = NULL; // 다음 노드를 이어주는 링크를 NULL로 초기화 시킨다.
        newNode->PrevLink = NULL; // 이전 노드를 이어주는 링크를 NULL로 초기화 시킨다.

        if (Head != NULL) { // 노드를 처음 추가하는 것이 아니라면
            Tail->NextLink = newNode; // 꼬리 노드의 다음 노드를 새로 추가된 노드로 지정한다
            newNode->PrevLink = Tail; // 새로 추가된 노드의 이전 노드를 꼬리 노드로 지정한다
            Tail = newNode; // 꼬리 노드를 새로 추가된 노드로 지정한다
        }
        else { // 노드를 처음 추가하는 것이라면
            Head = Tail = newNode; // 새로 추가한 노드를 헤드로 지정한다
        }
    }

    void deleteNode(string data)
    {
        Node* pNode = Head; // 임시 포인터에 헤드의 주소 값으로 초기화 한다

        if (pNode == NULL) return; // 한번도 추가하지 않았다면 그냥 빠져나온다
        else { // 노드가 하나만 존재하는 것이 아니라면
            Node* prevNode; // 이전 노드를 담을 Node 클래스 포인터
            Node* nextNode; // 다음 노드를 담을 Node 클래스 포인터
            do {
                // data와 pNode->data와 비교하여 일치하면 반복문을 빠져 나온다
                if (data.compare(pNode->data) == 0) break;
                pNode = pNode->NextLink; // 임시 노드에 다음 노드의 주소값을 대입한다.

            } while (pNode != NULL); // 임시 포인터의 주소값이 NULL이 될때까지 반복 
            prevNode = pNode->PrevLink; // 삭제하려는 노드의 이전 노드를 가리킨다
            nextNode = pNode->NextLink; // 삭제하려는 노드의 다음 노드를 가리킨다

            // 삭제하려는 노드의 이전 노드가 없으면 헤드(Head) 노드이므로 삭제하려는 노드의 다음 노드를 헤드 노드로 지정
            if (prevNode == NULL) Head = nextNode;
            // 위의 경우가 아니라면 삭제하려는 노드의 이전 노드가 삭제하려는 노드의 다음 노드를 가리키게 한다
            else prevNode->NextLink = nextNode;
            // 삭제하려는 노드의 다음 노드가 없으면 테일(Tail) 노드이므로 삭제하려는 노드의 이전 노드를 테일 노드로 지정
            if (nextNode == NULL) Tail = prevNode;
            // 위의 경우가 아니라면 삭제하려는 노드의 다음 노드가 삭제하려는 노드의 이전 노드를 가리키게 한다
            else nextNode->PrevLink = prevNode;
            delete pNode; // pNode를 메모리 공간에서 해제시킨다
        }
    }
    
    void printNode() {
        Node* tempPoint = Head; // 임시 포인터를 생성하고 이 포인터에 헤드의 주소 값을 대입

        // 노드가 하나도 존재하지 않으면 함수를 빠져나옴
        if (tempPoint == NULL) { cout << "리스트가 비어 있습니다." << endl; return; }
        // 노드가 하나만 존재할 경우
        if (tempPoint->NextLink == NULL) { cout << tempPoint->data << "->" << "NULL" << endl; }
        // 노드가 하나가 아닌 하나 이상 존재할 경우
        else {
            while (tempPoint != NULL) // 임시 포인터가 NULL이 될때까지 반복
            {
                cout << tempPoint->data << "<->"; // 임시 포인터의 데이터를 출력한다
                tempPoint = tempPoint->NextLink; // 임시 포인터의 NextlINK의 값을 대입한다
            }
            cout << "NULL" << endl; // 마지막에는 노드가 없음을 나타내기 위해 NULL 표시/개행
        }
    }
};

int main()
{
    DLL List;
    List.appendNode("빨강");
    List.appendNode("주황");
    List.appendNode("노랑");
    List.printNode();
    List.deleteNode("노랑");
    List.deleteNode("주황");
    List.deleteNode("빨강");
    List.printNode();
    return 0;
}

결과

빨강<->주황<->노랑<->NULL

리스트가 비어 있습니다.

계속하려면 아무 키나 누르십시오...

위의 예제에서의 메인 함수는 SLL이 DLL로 바뀐 것 말고는 다른 게 없습니다. 단순 연결 리스트만 완벽히 이해하고 계시면, 이중 연결 리스트를 구현하는 것도 크게 어렵지 않게 구현하실 수 있습니다. 이 예제의 함수에는 추가, 삭제, 출력 같은 기본적인 함수밖에 존재하지 않지만, 좌측 삽입, 우측 삽입, 노드의 수를 구하는 함수도 한번 만들어보세요.

더블 링크드 리스트(Doubly Linked List)