[자료구조] Doubly Linked List

*** 개인이 공부한 내용들을 간략하게 정리하고 참고하기 위한 포스팅입니다. 설명에 실수가 있을 수 있습니다. 지적해 주시면 정말 감사하겠습니다. ***

 

Singly Linked List에서는 각 node가 바로 다음 node로의 link만 가지고 있기 때문에, 임의의 node에 선행하는 노드를 파악할 수 없었다. 이로 인해 임의의 중간 지점 혹은 맨 끝에 있는 node를 삭제하려 할 때 필연적으로 비효율이 발생하였다. 

 

Doubly Linked List는 각 node가 (이전 node로의 link, 값, 다음 node로의 link)로 이루어져 있으며, 맨 앞과 뒤에 각각 header, trailer라는 dummy node가 덧붙여져 있다.(sentinel, guard라고도 한다.) 이러한 구조로 인해 임의의 중간 지점에 대한 insertion/deletion 연산을 O(1) time으로 수행할 수 있다.

 

Michael T. Goodrich, Data Structure&Algorithms 6th edition, Wiley, p. 132

 

 

Doubly Linked List의 insertion 연산의 경우, 추가하려는 node를 앞, 뒤 node와 연결하고, 앞,  뒷 node의 next/prev link를 새로 추가한 node와 적절히 연결하면 된다. 반대로 deletion의 경우, 삭제하려는 node의 앞, 뒷 node를 찾아서 각각의 prev, next link가 서로를 연결하도록 바꿔 주면 된다. 

 

간략하게 의사코드 느낌으로 만들어 봤다.

struct DLLNode
{
    DLLNode *prevNode;
    int value;
    DLLNode *nextNode;
};

void insertion(int e, DLLNode *prev, DLLNode *next)
{
    DLLNode *newNode = new DLLNode{nullptr, e, nullptr};

    newNode->nextNode = next;
    newNode->prevNode = prev;
    prev->nextNode = newNode;
    next->prevNode = newNode;
    size++;
}

void deletion(DLLNode *node)
{
    DLLNode *prev = node->prevNode;
    DLLNode *next = node->nextNode;

    prev->nextNode = next;
    next->prevNode = prev;

    delete node;
    size--;
}