[자료구조]이중 연결 리스트(Doubly Linked List)

참고 : <단순 연결 리스트>

이중 연결 리스트는 단순 연결 리스트와 함께 가장 많이 사용되는 연결 리스트의 형태이다. 단순 연결 리스트가 다음의 노드를 가리키는 하나의 링크를 가져서 바로 전의 노드를 알 수 없던 단점에 비해서, 이중 연결 리스트는 다음의 노드를 가리키는 링크와 전의 노드를 가리키는 링크 두 가지를 가져서 바로 전의 노드에도 접근할 수 있다는 것이 가장 큰 장점이다. 물론 하나의 링크를 더 사용하기 때문에 단순 연결 리스트보다는 메모리를 더 소모 한다. 

이중 연결 리스트의 Node 구조이다. 

typedef struct _dnode{
    int key;                // 정보
    struct _dnode *prev;    // 전 노드링크
    struct _dnode *next;    // 다음 노드링크
} dnode;

이중 연결 리스트를 구현하는 지원 함수들은 단순 연결 리스트에 비해 일관된 방식을 가지고 있다. 그 이유는 바로 전의 노드를 몰라서 애먹는 경우가 없기 때무닝다. 다만 노드를 삽입하거나 삭제할 때 많은 경우가 네 개의 링크를 조작해야 하기 때문에 조금 복잡하다는 단점이 있다. 

#include <stdio.h>
 
typedef struct _dnode{
    int key;
    struct _dnode *prev;
    struct _dnode *next;
} dnode;
 
 
dnode *head = NULL;
dnode *tail = NULL;
 
void init_dlist(void){
    head = (dnode*)malloc(sizeof(dnode));
    tail = (dnode*)malloc(sizeof(dnode));
    head->next = tail;
    head->prev = head;
    tail->prev = head;
    tail->next = tail;
}
 
dnode* find_dnode(int k){
    dnode *s;
    s = head->next;
    while (s->key != k && s != tail){
        s = s->next;
    }
 
    return s;
}
 
int delete_dnode(int k){
    dnode *s;
    s = find_dnode(k);
 
    if (s != tail){
        s->prev->next = s->next;
        s->next->prev = s->prev;
        free(s);
        return 1;
    }
    return 0;
}
 
dnode* insert_dnode(int k, int t){
    dnode *s;
    dnode *i = NULL;
    s = find_dnode(t);
 
    if (s != tail){
        i = (dnode*)malloc(sizeof(dnode));
        i->key = k;
        s->prev->next = i;
        i->prev = s->prev;
        s->prev = i;
        i->next = s;
    }
 
    return i;
}
 
dnode* ordered_insert(int k){
    dnode *s;
    dnode *i;
    s = head->next;
    while (s->key <= k && s != tail){
        s = s->next;
    }
 
    i = (dnode*)malloc(sizeof(dnode));
    i->key = k;
    s->prev->next = i;
    i->prev = s->prev;
    s->prev = i;
    i->next = s;
    return i;
}
 
int delete_dnode_ptr(dnode* p){
    if (p == head || p == tail){
        return 0;
    }
 
    p->prev->next = p->next;
    p->next->prev = p->prev;
    free(p);
    return 1;
}
 
dnode *insert_dnode_ptr(int k, dnode* t){
    dnode *i;
    if (t == head)
        return NULL;
 
    i = (dnode*)malloc(sizeof(dnode));
    i->key = k;
    t->prev->next = i;
    i->prev = t->prev;
    t->prev = i;
    i->next = t;
 
    return i;
}
 
void print_dlist(dnode *p){
    printf("\n");
    while (p != tail){
        printf("%-8d", p->key);
        p = p->next;
    }
}
 
void delete_all(void){
    dnode *p;
    dnode *s;
    
    p = head->next;
    while (p != tail){
        s = p;
        p = p->next;
        free(p);
    }
 
    head->next = tail;
    tail->prev = head;
}
 
void main(void){
 
    dnode *t;
    init_dlist();
 
    ordered_insert(10);
    ordered_insert(5);
    ordered_insert(8);
    ordered_insert(3);
    ordered_insert(1);
    ordered_insert(7);
    ordered_insert(8);
 
    printf("\nInitial Linked list is ");
    print_dlist(head->next);
 
    
    printf("\nFinding 4 is %ssuccessful", find_dnode(4) == tail ? "un" : "");
    
    t = find_dnode(5);
    printf("\nFinding 5 is %ssuccessful", t == tail ? "un" : "");
 
 
}

실제로 이중 연결 리스트는 많이 사용이 된다. 특히 활용이 많은 곳은 에디터나 워드프로세서이며 여기서 이중 연결 리스트는 문자을 저장하는 가장 적절한 방법으로 간주된다. 왜냐하면 워드프로세서의 문장들은 그 크기가 자주 변하고, 재배치되는 경우도 빈번하다. 그렇기 때문에 이중 연결 리스트를 사용할 경우 자료의 크기 변화나 재배치에 효율적이다. 그리고 이중 연결 리스트는 앞 뒤 링크를 모두 가지고 있어 문장간의 이동도 용이하다.