[Data Structure] #1-4 이중 원형 연결 리스트 (Circular Doubly Linked List)

이중 원형 연결 리스트 (Circular Doubly Linked List)

 #1-3 에서 우리는 원형 연결 리스트를 다루었다. 이제 이중 연결 리스트를 다뤄보자. 이중 연결리스트에서는 노드가 자신의 앞에 있는 노드가 무엇인지 알게 된다. 연결리스트가 자신의 다음 노드만을 가리켰으나 이중 연결리스트는 양쪽을 다 가리키게 된다. 공간을 많이 차지하게 되고 복잡해 진다는 단점이 있으나 선행 노드를 쉽게 찾을 수 있다는 장점이 있다.

 여기서는 원형 리스트를 혼합한 형태로 이중 연결리스트를 구현할 것이다.(그렇다고 복잡하거나 하지는 않다.. 워낙 심플한 코드라). 이중 원형 연결 리스트에는 Head Node가 존재한다. head pointer와 구별해야한다. head pointer는 첫 node를 가리키는 포인터이고 head node는 어떤 데이터도 가지지 않은 node인데 head의 역할을 하는 노드이다.

 코드를 보자.

#include <stdio.h>
#include <stdlib.h>

typedef int element;
typedef struct DlistNode{
    element data;
    struct DlistNode* llink;
    struct DlistNode* rlink;
} DlistNode;

void init(DlistNode *phead){
    phead->llink = phead;
    phead->rlink = phead;
}

void ddisplay(DlistNode *phead){
    DlistNode *p = phead->rlink;
    while (p != phead) {
        printf("<-- | %x | %d | %x | -->\n",p->llink,p->data,p->rlink);
        p = p->rlink; 
    }
}

void dinsert_node(DlistNode *before, DlistNode *new_node){
    new_node->llink = before;
    new_node->rlink = before->rlink;
    before->rlink->llink = new_node;
    before->rlink = new_node;
}

void dremove_node(DlistNode *phead_node, DlistNode *removed){
    if (phead_node == NULL) return;
    removed->llink->rlink = removed->rlink;
    removed->rlink->llink = removed->llink;
    free(removed);
}

int main() {
    DlistNode head_node;
    DlistNode *p[10];
    int i;
    init(&head_node);
    for (i=0; i<5; i++) {
        p[i] = (DlistNode *) malloc(sizeof(DlistNode));
        p[i]->data = i;
        dinsert_node(&head_node, p[i]);
    }
    dremove_node(&head_node, p[4]);
    ddisplay(&head_node);
    return 0;
}

 아래의 그림은 원형 연결리스트를 조금 더 이해하기 쉽게 해줄 것이다. :)

 항상 insert 할 때에는 new_node가 먼저 가리키도록 해야한다. 그리고 나서 before 노드와 after 노드가 new_node를 가리키게 한다. 나머지는 쉬운 부분이니 자세한 설명은 생략한다. (자세한 설명을 원하시면 책을 사셔서 보거나 질문 주세요 )