[Data Structure] 이중 연결 리스트(doubly linked list)

---

이중 연결 리스트

 

 

연결 리스트를 원형으로 구현해도 자신을 가리키는 노드에는 접근할 수 없었기 때문에 근본적인 단점이 있었다. 이를 해결하기 위해 노드 링크를 좌측 노드 링크와 우측 노드 링크로 나누어 저장하는 이중 연결 리스트를 활용할 수 있다.

이중 연결 리스트는 사용하는 노드가 링크를 좌측과 우측 두 개를 가지기 때문에 양방향 탐색이 가능하다. 단 그만큼 각 노드가 차지하는 메모리 공간이 크기 때문에 단점 역시 존재한다. 또한 장점을 살리려면 구현이 까다롭다는 단점이 있다.

이중 연결 리스트는 단일 연결 리스트나 원형 연결 리스트처럼 헤드 포인터를 사용하는 것이 아니라 헤드 노드를 이용한다. 헤드 노드는 데이터가 없는 노드이다. 헤드 노드를 사용하여 시작 노드와 마지막 노드를 각각 우측 링크와 좌측 링크에 저장한다.

 

---

연산

 

이중 연결 리스트도 단일 연결 리스트에서의 연산과 크게 다르지 않다. 삽입 삭제를 하면서 링크를 두 개 더 다룰 뿐이다. 예를 들어 아래는 기본적인 이중 연결 리스트의 형태이다.

삽입을 위해 새로운 노드를 만들고, 그 노드를 삽입하려는 위치에 넣어준다. 먼저 새로 만든 노드의 좌측 링크와 우측 링크를 알맞게 연결해준다.

그 후 삽입 하려는 노드를 우측 링크로 가리켜야 하는 이전 노드의 우측 링크가 삽입노드를 가리키게 만들고, 삽입노드를 좌측 링크로 가리켜야 하는 이전 링크가 우측 링크로 가리키고 있던 노드가 삽입 링크를 좌측 링크로 가리키게 만든다.

위 순서가 중요한 이유는 기본적으로 삽입 연산에서는 자신을 우측 링크로 가리키는 노드의 주소만을 활용하기 때문이다. 만약 삽입하려는 노드의 링크를 업데이트 하기 전에 이전 노드의 우측 링크가 삽입하려는 노드를 가리키게 만든다면 삽입하려는 노드를 좌측 링크로 가리켜야 하는 노드를 찾을 수 없다. 따라서 순서를 유의하여 연산을 구현하는 것이 중요하다.

삭제는 역으로 하면 된다.

위와 같이 삭제할 노드를 찾는다.

그 후 삭제할 노드가 좌측 링크로 가리키고 있는 노드가 삭제할 노드가 우측 링크로 가리키고 있는 노드를 우측 링크로 가리키게 만들고, 삭제할 노드가 우측 링크로 가리키고 있는 노드가 삭제할 노드가 좌측 링크로 가리키고 있는 노드를 좌측 링크로 가리키게 만든다. 그 후 삭제할 노드에 할당된 동적 메모리를 해제하면 된다.

 

---

구현 | C

 

C 를 통해 구현하였다. 연산은 위와 같지만, 이중 연결 리스트의 장점인 양방향 탐색이 가능하다는 점을 이용하여 삽입이나 삭제할 노드를 찾는 시간을 줄였다.

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

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

typedef struct {
    Node* head;
    int length;
} LinkedList;

void init(LinkedList* L) {
    L->head = (Node*)calloc(1, sizeof(Node));
    L->head->llink = L->head;
    L->head->rlink = L->head;
    L->length = 0;
}

int is_empty(LinkedList* L) {
    return L->length == 0;
}

int get_length(LinkedList* L) {
    return L->length;
}

void insert(LinkedList* L, int pos, element item) {
    if (pos < 0 || pos > L->length) {
        printf("Invalid location\n");
        return;
    }
    Node* node = (Node*)calloc(1, sizeof(Node));
    node->data = item;
    Node* pre;
    if (pos == 0) {
        node->rlink = L->head->rlink;
        node->llink = L->head;
        L->head->rlink->llink = node;
        L->head->rlink = node;
    } else if (pos <= L->length / 2) {
        pre = L->head->rlink;
        for (int i = 0; i < pos - 1; i++) {
            pre = pre->rlink;
        }
        node->rlink = pre->rlink;
        node->llink = pre;
        pre->rlink->llink = node;
        pre->rlink = node;
    } else {
        pre = L->head->llink;
        for (int i = L->length; i > pos; i--) {
            pre = pre->llink;
        }
        node->rlink = pre->rlink;
        node->llink = pre;
        pre->rlink->llink = node;
        pre->rlink = node;
    }
    L->length++;
}

void insert_first(LinkedList* L, element item) {
    insert(L, 0, item);
}

void insert_last(LinkedList* L, element item) {
    insert(L, L->length, item);
}

void delete(LinkedList* L, int pos) {
    if (pos < 0 || pos >= L->length) {
        printf("Invalid location\n");
        return;
    }
    Node* removed;
    if (L->length == 1) {
        removed = L->head->llink;
        L->head->llink = L->head;
        L->head->rlink = L->head;
    } else if (pos > L->length / 2) {
        removed = L->head->llink;
        for (int i = 0; i < L->length - pos - 1; i++) {
            removed = removed->llink;
        }
        removed->llink->rlink = removed->rlink;
        removed->rlink->llink = removed->llink;
    } else {
        removed = L->head->rlink;
        for (int i = 0; i < pos; i++) {
            removed = removed->rlink;
        }
        removed->llink->rlink = removed->rlink;
        removed->rlink->llink = removed->llink;
    }
    free(removed);
    L->length--;
}

void delete_first(LinkedList* L) {
    delete(L, 0);
}

void delete_last(LinkedList* L) {
    delete(L, L->length - 1);
}

element get_entry(LinkedList* L, int pos) {
    if (pos < 0 || pos >= L->length) {
        printf("Invalid location\n");
        return -1;
    }
    Node* current;
    if (pos <= L->length / 2) {
        current = L->head->rlink;
        for (int i = 0; i < pos; i++) {
            current = current->rlink;
        }
    } else {
        current = L->head->llink;
        for (int i = L->length - 1; i > pos; i--) {
            current = current->llink;
        }
    }
    return current->data;
}

void print_list(LinkedList* L) {
    if (is_empty(L)) {
        printf("NULL\n");
    } else {
        Node* current = L->head->rlink;
        for (int i = 0; i < L->length; i++) {
            printf("%d -> ", current->data);
            current = current->rlink;
        }
        printf("First Node\n");
    }
}