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

원형 연결 리스트(circular linked list)

원형 연결 리스트는 마지막 노드의 링크가 첫번째 노드를 가리키는 리스트를 말한다. 그렇기 때문에 한 노드에서 다른 모든 노드로 접근이 가능하게 된다.

보통 헤드포인터가 마지막 노드를 가리키게 구성하여 리스트의 처음이나 마지막 삽입을 더 용이하게 만든다.

이중 연결 리스트(doubly linked list)

이중 연결 리스트는 하나의 노드에서 두 개의 링크를 갖게 되는데 선행 노드와 후속 노드에 주소를 각각의 링크에 연결시켜 양뱡향 겁색이 가능하게끔 하는 리스트이다.

단순 연결 리스트에서 삽입과 삭제를 위해서는 선행노드의 주소가 반드시 필요했던 것과 달리 이중 연결 리스트는 양방향 검색이 가능하기 때문에 삽입,삭제를 더 용이하게 진행할 수 있다.

실제로 이중 연결과 원형 연결을 같이 구현하여 이중 원형 리스트를 가장 많이 사용한다고 한다.

오늘은 이중 연결 리스트를 더 자세하게 알아보자.

이중 연결 리스트(doubly linked list)

헤더노드(header node)

헤더노드는 리스트의 가장 처음에 나오는 노드로 데이터를 갖지 않고 헤드포인터와는 구별이 필요하다. 리스트가 공백인 상태에서는 헤더노드만 존재한다.

이중 원형 리스트의 구현

노드의 구조

typedef int element;
typedef struct DlistNode{
       element data;
       struct DlistNode *llink; //왼쪽 링크
       struct DlistNode *rlink; //오른쪽 링크
} DlistNode; //노드 정의

insert 함수의 구현(삽입)

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

delete 함수의 구현(삭제)

void ddelete_node(DlistNode *head, DlistNode *removed)
{    
     if(removed == head) return; //이건 공백이라는 뜻임, 공백이어도 헤더노드는 있으니까
     removed->rlink->llink = removed->llink;
     removed->llink->rlink = removed->rlink;
     free(removed); //메모리 반납

전체 코드 구현

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

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

void display(DlistNode *head)
{
    DlistNode *p;
    p = head->rlink;
    while (p != head){
        printf("%d ", p->data);
        p = p->rlink;
    }
    printf("\n");

}

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 *head, DlistNode *removed){
    
    if(removed == head) return;
    removed->llink->rlink = removed->rlink;
    removed->rlink->llink = removed->llink;
    free(removed);
}


int main()
{
    DlistNode    header;
    DlistNode    *before, *new_node;
    int          data;

    header.llink = &header;
    header.rlink = &header; //header node 구성 

    before = &header;
    
    do {
        scanf("%d", &data);
        if (data == -1) break;
        new_node = (DlistNode*)malloc(sizeof(DlistNode)); //노드 생성
        new_node->data = data;
        dinsert_node(before, new_node); //리스트 삽입
        before = new_node;
    } while (1);

    // 출력
    display(&header);
    // 마지막 노드 삭제
    dremove_node(&header, header.llink);
    // 출력
    display(&header);
}

헤더노드를 포함한 이중원형 연결 리스트

헤더노드의 rlink가 첫번째 노드를 가리키고 llink가 마지막 노드를 가리키며 원형으로 순환한다.

[참고자료]

https://kangdy25.tistory.com/82

https://jow1025.tistory.com/217