[C] 이중 연결 리스트(Doubly Linked List)

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

• 응용 프로그램에서의 특정 노드에서 양방향으로 자유롭게 움직일 수 있는 리스트 구조
• 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트
• 링크가 양방향이므로 양방향으로 검색이 가능해진다.
• 공간을 많이 차지하고 코드가 복잡해진다는 단점이 있다.
• 실제 응용에서는 이중 연결 리스트와 원형 연결 리스트를 혼합한 형태가 많이 사용된다.
• 헤드 노드(Head Node)라는 특별한 노드를 추가하는 경우가 많다.
• 헤드 노드는 데이터를 가지고 있지 않은 특별한 노드를 의미한다.
  • 헤드 포인터 : 리스트의 첫 번째 노드를 가리키는 포인터
• 헤드 노드가 존재하면 삽입, 삭제 알고리즘이 간편해진다.
• 이중 연결 리스트에서의 노드는 3개의 필드(왼쪽 링크 필드, 데이터 필드, 오른쪽 링크 필드)로 이루어져 있다.
• 링크 필드에는 포인터가 저장된다.

 

코드

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <string.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 display(DlistNode *phead) {
    DlistNode *p;
    for (p = phead->rlink; p != phead; p = p->rlink) {
        printf("<--- | %x | %d | %x | ---->\n", p->llink, p->data, p->rlink);
    }
    printf("\n");
}

// 노드 new_node를 노드 before의 오른쪽에 삽입
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;
}

// 노드 removed를 삭제
void dremove_node(DlistNode *phead_node, DlistNode *removed) {
    if (removed == phead_node) return;
    removed->llink->rlink = removed->rlink;
    removed->rlink->llink = removed->llink;
    free(removed);
}

// 원하는 원소를 탐색
DlistNode *dsearch(DlistNode *head_node, element x) {
    DlistNode *p;
    p = head_node;
    do {
        if (p->data == x) return p;        // 탐색 성공
        p = p->rlink;                        // 오른쪽 링크따라 이동
    } while (p != head_node);

    return NULL;                            // 탐색 실패
}

// 두 리스트를 연결
DlistNode *dconcat(DlistNode *head1, DlistNode *head2) {
    if (head1 == head1->rlink) return head2;                    // head1이 공백인 경우
    else if (head2 == head2->rlink) return head1;                // head2가 공백인 경우
    else {        // 둘 다 공백이 아닌 경우
        head2->rlink->llink = head1->llink;
        head1->llink->rlink = head2->rlink;
        head2->llink->rlink = head1;
        head1->llink = head2->llink;
        head2->rlink = head2;
        head2->llink = head2;

        return head1;
    }
}

// 모든 노드를 삭제
DlistNode dremove_all(DlistNode *head_node) {
    DlistNode *removed = head_node->rlink;            // head노드의 오른쪽 노드 삭제
    if (head_node == head_node->rlink) return;        // 공백이면 종료
    while (removed != head_node) {        // 삭제할 노드가 head가 아닌 동안 반복
        removed->llink->rlink = removed->rlink;
        removed->rlink->llink = removed->llink;
        free(removed);
        removed = head_node->rlink;
    }
}


// 교재 main 함수 수정
void main() {
    DlistNode head_node, head_node2;
    DlistNode *phead_node = &head_node;
    DlistNode *p[10], *p2[10];
    int i;
    init(&head_node);
    init(&head_node2);

    for (i = 0; i < 5; i++) {
        p[i] = (DlistNode *)malloc(sizeof(DlistNode));
        p[i]->data = i;
        // 헤드 노드의 오른쪽에 삽입
        dinsert_node(&head_node, p[i]);
    }
    display(&head_node);
    getchar();

    if (dsearch(&head_node, 3)) printf("찾음\n");
    else printf("없음\n");
    
    if (dsearch(&head_node, 10)) printf("찾음\n");
    else printf("없음\n");

    dremove_node(&head_node, p[4]);
    display(&head_node);
    getchar();

    for (i = 0; i < 5; i++) {
        p2[i] = (DlistNode *)malloc(sizeof(DlistNode));
        p2[i]->data = i+10;
        // 헤드 노드의 오른쪽에 삽입
        dinsert_node(&head_node2, p2[i]);
    }

    display(&head_node2);
    getchar();
    phead_node = dconcat(&head_node, &head_node2);
    display(&head_node);
    getchar();
    dremove_all(&head_node);
    display(&head_node);
    getchar();
}