C++ 이중 연결 리스트(double linked list) 설명 및 예제

일반적인 링크드 리스트는 Node가 다른 Node를 하나만 가리키고 있지만 이중 연결리스트는 앞 뒤로 하나씩 연결을 가지고 있습니다. 

그래서 탐색을 할때 해당 노드에서 앞에 노드나 뒤에 노드로 쉽게 왔다갔다 할 수 있는 장점이 있습니다. 특정 노드를 탐색하다가 뒤로 마음대로 갈 수 있다는 의미이다. 프로그램을 작성하기전에 이러한 상황이 꼭 필요하고 자주 발생할 것 같다면 이중 연결 리스트를 고려해 보아야 합니다. 

  

아래 Node를 보면 next와 prev 라는 2개의 Node 포인터를 볼 수 있습니다. 하나는 자신의 앞에 있는 노드(next)를 가르키며 다른하나는 자신의 뒤에 있는 노드(prev)를 가르키는 역할을 합니다.

생성자를 통해 기본적으로 포인터에 NULL을 대입 합니다. 그리고 파라미터를 받는 생성자는 파마리터로 받은 ptr을 가지고 해당 노드 다음에 자신을 놓도록 합니다. 포인터를 사용하기 때문에 복잡해 보일 수 있다. 종이에 하나하나 그려가며 코드를 보면 이해가 쉽게 갈 것입니다.

struct Node { 
    int data;
    Node* next, * prev; 
    Node() {
        next = prev = NULL;
        data = 0;
    }
    Node(int i, Node* ptr)//ptr 뒤에 추가
    {
        data = i;
        prev = ptr;
        next = ptr->next;
        next->prev = prev->next = this; 
    }  
};

 

그리고 이중 연결리스트의 또 다른 장점으로는 노드 자신을 삭제하는게 쉽습니다. 그 이유는 자신의 앞에노드와 뒤에 노드의 정보를 가지고 있기 때문에 포인터를 가지고 자신을 제외한 앞뒤 포인터를 서로 연결 시켜줄 수 있어서 입니다.

아래 예시는 자기 자신의 노드를 삭제하는 함수 입니다. 함수의 첫번째 줄은 자신의 뒤에 노드에 다음을 가르키는 포인터에 자기 자신의 다음 노드의 주소값을 넘겨줍니다. 그러면 뒤에 노드가 자신의 다음 노드를 가르키게 하는 것입니다. 두번째 줄에는 자신의 다음노드의 이전을 가르키고 있는 포인터에 자신이 가르키고 있는 뒷노드의 주소값을 넘겨주는 것입니다. 그리고 마지막으로 delete로 자기자신을 삭제해서 할당받은 메모리를 해제합니다. 간결한 코드이지만 처음이해하는데는 많은 어려움이 있을 수 있습니다.

void selvDelete() {
     prev->next = next;
     next->prev = prev;
     delete this;
}

일반적으로 간단하게 데이터를 추가하고 탐색하는 경우에는 일반 연결 리스트를 구현하면 됩니다.

연결리스트를 활용하여 구현한 Stack 예제 : http://hijuworld.tistory.com/54

하지만 데이터를 탐색할 때 뒤로 갔다 앞으로 갔다하는 경우가 많고 데이터 삭제가 빈번한 경우라면 이중 연결 리스트로 구현하는 것이 좋습니다.

아래 예제는 이중연결리스트를 구현한 예제입니다.

C++을 기본으로 작성하였으며 데이터를 삽입이나 삭제 할때 가장 앞이나 가장 뒤에서 모두 가능하게 하였습니다.

필요한 기능의 함수가 있다면 DLinkedList 구조체에 추가하여 구현하면 됩니다. 

해당 예제를 가지고 데이터를 앞뒤로 삽입하고 삭제하기 때문에 왠만한 기능을 다 할 수 있습니다.

#include<iostream>
 
 
struct Node {
    int data;
    Node* next, * prev;
    Node() {
        next = prev = NULL;
        data = 0;
    }
    Node(int i, Node* ptr)//ptr 뒤에 추가한다.
    {
        data = i;
        prev = ptr;
        next = ptr->next;
        next->prev = prev->next = this; 
    }    
    void selvDelete() {
        prev->next = next;
        next->prev = prev;
        delete this;
    }
};
 
struct DLinkedList {
    Node *head;
    Node *tail;
    int count;
    DLinkedList() { //생성자
        count = 0;
        head = new Node(); //더미를 선언해서 가지고 있게한다.
        tail = new Node(); //더미를 선언해서 가지고 있게한다.
        head->next = tail; //서로연결한다.
        tail->prev = head;
    }
    ~DLinkedList() {
        while (head->next != tail)
            head->next->selvDelete();
        delete head;
        delete tail;
    }
    void firstInsert(int i) { //head 다음에 추가한다.
        new Node(i, head);
    }
    void endInsert(int i) { //tail 앞에 추가한다.
        new Node(i, tail->prev);
    }
    void firstDelete() { //head 다음 노드 삭제한다.
        if (head->next == tail)    return;
        head->next->selvDelete();
    }
    void endDelete() { //tail 앞에 제거한다.
        if (tail->prev == head) return;
        tail->prev->selvDelete();
    }
    void printAll() {
        Node* tmp = head;
        while (tmp->next != tail) {
            printf("%d\n", tmp->next->data);
            tmp = tmp->next;
        }
    }
};
 
int main() {
    DLinkedList *list = new DLinkedList();
    list->firstInsert(1); //1을 삽입한다.(가장앞)
    list->firstInsert(3); //3을 삽입한다.(1앞에)
    list->firstInsert(5); //5을 삽입한다.(3앞에)
    list->firstDelete(); //5를 삭제한다
    list->endInsert(100); //100을 삽입한다.(가장뒤에)
    list->endInsert(200); //200을 삽입한다.(100뒤에)
    list->endInsert(300); //300을 삽입한다.(200뒤에)
    list->endDelete(); //300을 삭제한다.
    list->printAll();
    delete list;
}

 이중 연결리스트를 여러번 직접 종이에 그려가며 작성해 보아야 손에 익어서 언제든 작성 할 수 있습니다. 처음부터 코드를 완벽하게 작성하고 실행을 해야합니다. 대충 작성하고 디버깅을 해야지 하고 생각한다면 쉽게 에러를 찾을 수 없습니다. 포인터를 가지고 계속 왔다갔다 하기 때문에 디버깅에 많은 어려움이 있습니다. 연결 리스트 뿐만 아니라 데이터를 포인터로 연결하는 트리나 링큐 등도 디버깅하는데 많은 어려움이 있습니다. 처음부터 주의깊게 프로그래밍하는 것이 좋습니다.