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

 

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

이중 연결 리스트는 한 노드에 link 멤버가 두 개 있는 연결 리스트를 말합니다.

 

이전에 설명한 단순 연결 리스트와 원형 연결 리스트는 노드 탐색을 하든, 출력을 하든 항상 다음 노드를 찾아가는 방식이었습니다. 그러나 이 둘은 이전 노드를 탐색하려면 번거로운 과정을 거쳐야 합니다.

일방통행 도로의 차량 통행 방식과 같은 단순 연결 리스트 노드 접근 방식

실생활에 예를 들자면 일방통행 도로를 생각해볼 수 있겠네요. 가고싶은 장소가 있는데 모르고 지나쳤을 때 다시 돌아가려면 어떻게 해야하나요? 후진해서 지나친 곳을 갈 수 있겠지만, 도로 상황이 번잡하고 무조건 한 방향으로만 움직여야 한다면 빙 돌아서 그 도로를 다시 진입해야겠죠. 지금까지 구현한 리스트는 그런 방식이었습니다.

이중 연결 리스트는 이러한 번거로움을 방지하고자 link 멤버를 하나 더 구현합니다. 그리고 두 개의 link 멤버를 각각 왼쪽(llink; left link), 오른쪽(rlink; right link)으로 정합니다. 그렇게 되면 llink는 이전 노드를 가리키고 있고 rlink는 다음 노드를 가리키는 방식이 됩니다.

 

이러한 이중 연결 리스트는 실생활에서 굉장히 많이 쓰입니다. 특히 앞으로 가기와 뒤로 가기를 사용해야 하는 로직에서는 대부분 사용됩니다. 대표적으로 웹 브라우저가 있습니다. 우리가 웹페이지에 접속하고자 새 탭을 열어서 10개의 페이지를 방문했다고 가정해봅시다. 문득 이전에 방문한 페이지를 다시 접속해야 한다고 했을 때, 뒤로가기(Alt + ←) 버튼을 눌러 방문하고 다시 돌아가려면 앞으로 가기(Alt + →) 버튼을 눌러 방문합니다. 노래를 스트리밍하는 사이트에 접속해서 어떻게 노래를 재생하는지 살펴보면 비슷함을 느낄 수 있을 것입니다.

 

함수별로 어떻게 동작하는지 살펴보겠습니다.

 

insert_node(*head, *removed)

이중 연결 리스트에 노드를 삽입하는 과정은 다음과 같습니다.

1. 새로운 노드인 node를 동적으로 메모리 할당한다.
2. node의 data 멤버에 함수의 parameter로 넘어온 data 값을 넣어준다.
3. node의 왼쪽 포인터( == llink 멤버 )가 이전 노드를 가리킨다.
4. node의 오른쪽 포인터( == rlink 멤버 )가 이전 노드가 오른쪽 포인터로 가리킨 노드를 가리킨다. 즉, 이전 노드 대신 node가 다음 노드를 가리킨다.
5. 이전 노드의 오른쪽 포인터가 가리키는 노드( == 다음 노드 )의 왼쪽 포인터가 node를 가리킨다.
6. 이전 노드의 오른쪽 포인터가 node를 가리킨다.

void insert_node(DListNode *before, element data) {
    DListNode *node = (DListNode *)malloc(sizeof(DListNode)); // 1.
    node->data = data; // 2.
    node->llink = before; // 3.
    node->rlink = before->rlink; // 4.
    before->rlink->llink = node; // 5.
    before->rlink = node; // 6.
}

 

delete_node(*head, *removed)

이중 연결 리스트에 노드를 삭제하는 과정은 다음과 같습니다.

1. 삭제하려는 노드가 헤드 노드라면 함수를 그냥 종료한다.
2. 그렇지 않다면 지우려는 노드의 왼쪽 포인터가 가리키는 노드( == 이전 노드 )의 오른쪽 포인터를 지우려는 노드가 오른쪽 포인터로 가리키는 노드( == 다음 노드)를 가리킨다.
3. 그리고 지우려는 노드의 오른쪽 포인터가 가리키는 노드( == 다음 노드 )의 왼쪽 포인터를 지우려는 노드가 왼쪽 포인터로 가리키는 노드( == 이전 노드 )를 가리킨다.
4. removed 포인터 변수를 메모리 해제한다.

void delete_node(DListNode *head, DListNode *removed) {
    if(removed == head) return; // 1.
    removed->llink->rlink = removed->rlink; // 2.
    removed->rlink->llink = removed->llink; // 3.
    free(removed); // 4.
}

 

print_dlist(*phead)

헤드 노드에서부터 오른쪽 link 멤버를 통해 다음 노드로 나아가면서 다시 헤드 노드까지 돌아올 때 까지 각각의 노드들의 data를 출력합니다.

 

이를 구현하면 아래와 같습니다.

void print_dlist(DListNode *phead) {
    DListNode *p;
    for (p = phead->rlink; p != phead; p = p->rlink) {
        printf("<-| |%d| |-> ", p->data);
    }
    printf("\n");
}

 

전체 코드는 다음과 같습니다.

void insert_node(DListNode *before, element data) {
    DListNode *node = (DListNode *)malloc(sizeof(DListNode));
    node->data = data;
    node->llink = before;
    node->rlink = before->rlink;
    before->rlink->llink = node;
    before->rlink = node;
}

void delete_node(DListNode *head, DListNode *removed) {
    if(removed == head) return;
    removed->llink->rlink = removed->rlink;
    removed->rlink->llink = removed->llink;
    free(removed);
}

void print_dlist(DListNode *phead) {
    DListNode *p;
    for (p = phead->rlink; p != phead; p = p->rlink) {
        printf("<-| |%d| |-> ", p->data);
    }
    printf("\n");
}