양방향 연결 리스트(Doubly Linked List) 설명과 예제 코드(C++)

algorithm

단일 링크드 리스트는 한쪽 방향으로 탐색이 가능하지만 양방향은 앞,뒤 방향으로 모두 탐색이 가능한 링크드 리스트입니다. 단일 링크드 리스트의 장점을 갖고, 추가로 양방향으로 탐색할 수 있는 장점이 있습니다. 메모리는 포인터 변수가 하나만큼 양방향 리스트가 더 많이 소모됩니다.

완성된 코드는 GitHub - Doubly Linked List에 있습니다. 코드만 참고하시는 분들은 GitHub를 확인해주세요.

단일 연결 리스트는 단일 연결 리스트(링크드 리스트) 설명과 예제 코드(C++)에서 확인해주세요.

양방향 링크드 리스트 데이터 구조

데이터를 저장하는 단위를 노드라고 합니다. 노드는 데이터를 저장하는 data변수가 있고, 이전과 다음의 노드를 가리키는 포인터 객체 next와 prev를 갖고 있습니다.

typedef struct ListNode {
    int data;
    struct ListNode* next;
    struct ListNode* prev;
} ListNode;

그리고 링크드 리스트의 처음을 가리키는 head라는 변수가 있습니다. 데이터에 접근하려면 이 변수를 통해서 접근할 수 있습니다.

ListNode* head = NULL;

양방향 링크드 리스트에 데이터 삽입

데이터는 리스트의 첫번째 또는 원하는 위치에 삽입할 수 있습니다. 아래 코드는 리스트의 삽입 코드입니다. head에 아무 데이터가 없다면 가장 처음에 데이터가 삽입되고, 데이터가 있다면 인자로 전달된 position의 위치에 노드가 삽입됩니다. position의 값이 1이라면 가장 첫번째에 삽입됩니다. 데이터의 길이보다 position이 더 크다면 리스트의 가장 마지막에 노드가 삽입됩니다. 중요한 것은, 양방향 링크드 리스트이기 때문에 prev와 next를 빼먹지 않고 꼭 설정해줘야 합니다.

void DLLInsert(ListNode **head, int data, int position) {
    ListNode *inserted = new ListNode;
    inserted->data = data;
    if (*head == NULL || position == 1) {
        inserted->prev = NULL;
        inserted->next = *head;
        if (*head != NULL) {
            (*head)->prev = inserted;
        }
        *head = inserted;
    } else {
        ListNode *inserted_prev = *head;
        ListNode *inserted_next;
        for (int i = 1; i < (position-1) && inserted_prev->next != NULL; i++) {
            inserted_prev = inserted_prev->next;
        }

        inserted_next = inserted_prev->next;
        if (inserted_next == NULL) { // last item
            inserted_prev->next = inserted;
            inserted->prev = inserted_prev;
            inserted->next = NULL;
        }
        else {
            inserted_prev->next = inserted;
            inserted_next->prev = inserted;
            inserted->prev = inserted_prev;
            inserted->next = inserted_next;
        }
    }
}

링크드 리스트의 모든 데이터 출력

리스트의 길이를 구하는 코드와 같이 모든 리스트를 탐색하면서 데이터를 출력하면 됩니다.

void PrintList(struct ListNode* head) {
    ListNode* current = head;
    while (current != NULL) {
        cout << current->data << " -> ";
        current = current->next;
    }
    cout << "NULL\n";
}

링크드 리스트의 노드 삭제

위의 노드 삽입 코드와 같이, head에서 인자 position의 위치에 해당하는 노드를 삭제합니다. 삭제하려는 position에 노드가 없으면 가장 마지막 노드를 삭제합니다. 노드를 삭제하면, 그 주변의 노드들의 prev와 next를 빼먹지 않고 잘 설정해줘야 합니다.

void DLLDelete(ListNode **head, int position) {
    if (*head == NULL) {
        return;
    }

    ListNode *removed;
    ListNode *removed_next;
    ListNode *removed_prev;
    if (position == 1) {
        removed = *head;
        *head = (*head)->next;
        (*head)->prev = NULL;
        delete removed;
    }
    else {
        removed = *head;
        for (int i = 1; i < position && removed->next != NULL; i++) {
            removed = removed->next;
        }

        removed_next = removed->next;
        removed_prev = removed->prev;
        if (removed_next == NULL) { // last item
            removed_prev->next = NULL;
            delete removed;
        }
        else {
            removed_prev->next = removed_next;
            removed_next->prev = removed_prev;
            delete removed;
        }
    }
}

완성된 코드

완성된 코드는 GitHub - Doubly Linked List에 있습니다.

아래 코드처럼 데이터를 삽입, 삭제하여 링크드 리스트가 잘 구현되었는지 확인해볼 수 있습니다.

int main()
{
    DLLInsert(&head, 4, 1);
    PrintList(head);
    DLLInsert(&head, 10, 1);
    PrintList(head);
    DLLInsert(&head, 15, 2);
    PrintList(head);
    DLLInsert(&head, 13, 2);
    PrintList(head);
    DLLInsert(&head, 13, 10);
    PrintList(head);

    DLLDelete(&head, 1);
    PrintList(head);
    DLLDelete(&head, 10);
    PrintList(head);
    DLLDelete(&head, 2);
    PrintList(head);
}

실행 결과

4 -> NULL
10 -> 4 -> NULL
10 -> 15 -> 4 -> NULL
10 -> 13 -> 15 -> 4 -> NULL
10 -> 13 -> 15 -> 4 -> 13 -> NULL
13 -> 15 -> 4 -> 13 -> NULL
13 -> 15 -> 4 -> NULL
13 -> 4 -> NULL

참고

다음 글은 원형 연결 리스트(링크드 리스트) 설명과 예제 코드(C++)입니다.

Loading script...
codechachaCopyright ©2019 codechacha