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

이중 연결리스트란?

• 단순 연결리스트의 선행 노드가 찾기 힘들다는 점을 보완한 리스트
• 각 노드가 선행 노드와 후속 노드에 대한 링크를 가지는 리스트
• 노드의 left link와 right link가 각각 다른 노드의 오른쪽 링크와 왼쪽 링크를 연결짓는다.
• 헤드부분도 노드로 이루어져 있다.
• 단점은 공간을 많이 차지하고 코드가 복잡하다.

---

※ 헤드노드란?

헤드노드는 데이터를 가지지 않고 오로지 삽입, 삭제 코드를 간단하게 할 목적으로 만들어진 노드이다. 따라서 헤드 포인터와의 구별이 필요하며 리스트가 공백상태라면 헤드 노드만 존재하는 상태이다. 이때 헤드노드의 left link는 right link를 가리키며 right link는 left link를 가리키는 상태이다.

 

---

 

 

노드 구조체

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;
}

• data는 기존의 연결리스트와 같지만, link 대신에 llink와 rlink 2개를 멤버변수를 가진다.
• llink오 rlink는 phead로 초기화

---

 

 

삽입연산

1. new_node의 llink가 before를 가리킨다.
2. new_node의 rlink가 before의 rlink를 가리킨다.
3. before의 rlink의 llink가 new_node를 가리킨다.
4. before의 rlink가 new_node를 가리킨다.

// 새로운 데이터를 노드 before의 오른쪽에 삽입
void dinsert(DListNode* before, element data) {
    DListNode* newnode = (DListNode*)malloc(sizeof(DListNode));
    newnode->data = data;
    newnode->llink = before; // (1)
    newnode->rlink = before->rlink; // (2)
    before->rlink->llink = newnode; // (3)
    before->rlink = newnode; // (4)
}

---

 

 

삭제연산

1. removed의 llink의 rlink와 removed의 rlink와 연결한다.
2. removed의 rlink의 llink와 removed의 llink와 연결한다.

// 노드 removed를 삭제
void ddelete(DListNode* head, DListNode* removed) {
    if (removed == head) return;
    head->rlink = removed->rlink;
    removed->rlink->llink = removed->llink;
    free(removed);
}

---

 

 

전체코드

#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 print_dlist(DListNode* phead) {
    DListNode* p;
    for (p = phead->rlink; p != phead; p = p->rlink) {
        printf("<-| |%d| |-> ", p->data);
    }
    printf("\n");
}
// 새로운 데이터를 노드 before의 오른쪽에 삽입
void dinsert(DListNode* before, element data) {
    DListNode* newnode = (DListNode*)malloc(sizeof(DListNode));
    newnode->data = data;
    newnode->llink = before;
    newnode->rlink = before->rlink;
    before->rlink->llink = newnode;
    before->rlink = newnode;
}
// 노드 removed를 삭제
void ddelete(DListNode* head, DListNode* removed) {
    if (removed == head) return;
    head->rlink = removed->rlink;
    removed->rlink->llink = removed->llink;
    free(removed);
}
// 메인
int main(void) {
    DListNode* head = (DListNode*)malloc(sizeof(DListNode));
    init(head);
    printf("추가 단계\n");
    for (int i = 0; i < 5; i++) {
        dinsert(head, i);
        print_dlist(head);
    }
    printf("\n삭제 단계\n");
    for (int i = 0; i < 5; i++) {
        print_dlist(head);
        ddelete(head, head->rlink);
    }
    free(head);
    return 0;
}