왜 링크를 하나 더 두거나 순환시키는가

07편에서 다룬 단순 연결리스트는 next 링크 하나로 앞으로만 이동할 수 있다. 그래서 “현재 노드의 바로 앞 노드가 무엇인지”를 알아내려면 head부터 다시 처음부터 탐색해야 하는 불편함이 있다. 또한 마지막 노드는 NULL을 가리키고 있어서, “마지막까지 갔다가 다시 처음으로 돌아가야 하는” 상황(예: 여러 사용자가 자리를 돌아가며 순서를 갖는 라운드 로빈(round robin) 방식)을 자연스럽게 표현하지 못한다. 이 편에서 다루는 이중 연결리스트(doubly linked list)는 링크를 하나 더 두어 “뒤로도 갈 수 있게” 하고, 원형 연결리스트(circular linked list)는 마지막 노드가 다시 첫 노드를 가리키게 해 “끝나지 않고 순환하게” 만든다.

쉽게 말하면: 이중 연결리스트는 “앞뒤로 다 갈 수 있는 줄”이고, 원형 연결리스트는 “마지막 사람이 다시 첫 사람 손을 잡아 원을 이루는 줄”이다.

이중 연결리스트의 구조

이중 연결리스트의 노드는 데이터 필드 하나와 링크 필드 두 개(이전 노드를 가리키는 prev, 다음 노드를 가리키는 next)로 구성된다.

typedef struct DNode {
    int data;
    struct DNode *prev;  // 이전 노드를 가리키는 링크
    struct DNode *next;  // 다음 노드를 가리키는 링크
} DNode;

노드 3개가 연결된 이중 연결리스트를 그림으로 보면 다음과 같다. 첫 노드의 prev와 마지막 노드의 next는 각각 NULL이다.

이 구조 덕분에 어떤 노드를 손에 쥐고 있으면 node->prev로 바로 앞 노드에, node->next로 바로 뒤 노드에 $O(1)$로 이동할 수 있다. 단순 연결리스트에서는 “바로 앞 노드”를 알아내려면 head부터 다시 탐색해 $O(n)$이 걸렸던 것과 대조된다.

쉽게 말하면: 이중 연결리스트는 각 노드가 “내 앞 사람”과 “내 뒷 사람”을 모두 손에 쥐고 있어서, 어느 방향으로든 바로 한 걸음 움직일 수 있는 구조다.

이중 연결리스트의 삽입 — 링크 네 개를 정확한 순서로

10 ↔ 20 ↔ 30(양방향 연결, 첫 노드 prev는 NULL, 마지막 노드 next는 NULL)에서 20과 30 사이에 25를 삽입하는 과정을 추적해 보자. cur는 20 노드를 가리키는 포인터라고 하자.

void insertAfterD(DNode *cur, int value) {
    DNode *newNode = (DNode*)malloc(sizeof(DNode));
    newNode->data = value;
    newNode->next = cur->next;
    newNode->prev = cur;
    if (cur->next != NULL) {
        cur->next->prev = newNode;  // 원래 다음 노드의 prev부터 갱신
    }
    cur->next = newNode;            // 마지막에 cur의 next를 갱신
}

이중 연결리스트의 삽입은 단순 연결리스트보다 바꿔야 할 링크가 두 배(4개)이지만, 삽입 자체(위치를 이미 알고 있을 때)는 여전히 $O(1)$이다. 순서가 중요한 이유는 단순 연결리스트 때와 같다. cur->next = newNode를 먼저 실행해 버리면 그다음 줄에서 cur->next->prev가 이미 newNode를 가리키게 되어 원래의 30 노드에 접근할 방법이 사라진다.

자주 틀리는 점: 이중 연결리스트 삽입 문제에서 prev와 next 중 하나만 갱신하고 끝냈다고 착각하는 오류가 잦다. 새 노드 하나를 끼워 넣으려면 항상 4개의 링크(newNode->next, newNode->prev, 앞 노드의 next, 뒤 노드의 prev)를 전부 맞춰야 리스트가 정상적으로 연결된다.

이중 연결리스트의 삭제

10 ↔ 20 ↔ 30에서 20을 삭제하는 과정을 추적해 보자. target은 20 노드를 가리키는 포인터다.

void deleteNodeD(DNode *target) {
    if (target->prev != NULL) {
        target->prev->next = target->next;
    }
    if (target->next != NULL) {
        target->next->prev = target->prev;
    }
    free(target);
}

단순 연결리스트의 삭제는 “삭제할 노드의 바로 앞 노드”를 알아야만 가능했지만(그렇지 않으면 앞 노드부터 다시 탐색해야 했다), 이중 연결리스트는 삭제할 노드 자신만 알아도 target->prev로 바로 앞 노드에 접근할 수 있으므로 탐색 없이 바로 삭제할 수 있다는 것이 실질적인 이점이다.

이중 연결리스트의 역방향 순회

이중 연결리스트의 가장 뚜렷한 장점은 마지막 노드에서 시작해 거꾸로 순회할 수 있다는 것이다.

void printReverse(DNode *tail) {
    DNode *cur = tail;
    while (cur != NULL) {
        printf("%d ", cur->data);
        cur = cur->prev;  // 이전 노드로 이동
    }
    printf("\n");
}

10 ↔ 20 ↔ 30의 마지막 노드(tail, 값 30)부터 실행하면 다음과 같이 추적된다.

30 20 10

단순 연결리스트는 next만 있으므로 이런 역방향 순회를 하려면 전체를 스택에 담았다가 꺼내는 등 별도의 자료구조가 필요하지만(09편에서 스택을 배우면 그 방법을 이해할 수 있다), 이중 연결리스트는 prev만 따라가면 그대로 끝난다.

원형 연결리스트의 구조

원형 연결리스트(circular linked list)는 마지막 노드의 next가 NULL이 아니라 첫 노드를 다시 가리키게 만든 구조다. 단순 연결리스트를 원형으로 바꿀 수도 있고(단순 원형 연결리스트), 이중 연결리스트를 원형으로 바꿀 수도 있다(이중 원형 연결리스트, 이 경우 첫 노드의 prev도 마지막 노드를 가리킨다).

원형 연결리스트에서는 NULL을 “끝났다”는 판단 기준으로 쓸 수 없다. 대신 순회를 시작한 노드로 다시 돌아왔는지로 종료 조건을 판단해야 한다.

void printCircular(Node *head) {
    if (head == NULL) return;
    Node *cur = head;
    do {
        printf("%d ", cur->data);
        cur = cur->next;
    } while (cur != head);  // head로 돌아오면 종료
    printf("\n");
}

10 -> 20 -> 30 -> (다시 10) 원형 리스트에 대해 이 함수가 실행되는 과정을 추적하면 다음과 같다.

10 20 30

자주 틀리는 점: 원형 연결리스트를 while (cur != NULL)로 순회하도록 코드를 짜면 무한 루프에 빠진다. 원형 구조에는 애초에 NULL이 없으므로, 반드시 “시작 노드로 돌아왔는가”를 종료 조건으로 써야 한다. 이 함정은 시험에서 “다음 코드를 원형 연결리스트에 실행하면 어떻게 되는가”를 묻는 문제로 자주 나온다.

원형 연결리스트의 응용 감각

원형 연결리스트는 “순서대로 돌아가면서 처리해야 하는데, 끝에 도달해도 계속 이어져야 하는” 상황에 자연스럽게 들어맞는다. 대표적인 예가 라운드 로빈 스케줄링(round robin scheduling, 여러 작업에 순서대로 짧은 시간씩 CPU를 배정하고 마지막 작업 다음에는 다시 첫 작업으로 돌아가는 방식)이다. 또한 마지막 노드에 대한 포인터(tail)만 유지하면 tail->next가 곧 head이므로, 별도의 head 변수 없이도 리스트 전체를 표현할 수 있다는 구현상의 이점도 있다.

세 연결리스트 비교

07~08편에서 다룬 세 가지 연결리스트를 한 표로 정리하면 다음과 같다.

자주 틀리는 점

• 이중 연결리스트 삽입에서 링크 4개 중 일부만 갱신하는 오류: newNode의 prev·next, 그리고 양옆 기존 노드의 링크까지 총 4곳을 모두 맞춰야 한다.
• 원형 연결리스트를 NULL 검사로 순회하려는 오류: 원형 구조에는 NULL이 없으므로 무한 루프에 빠진다. 시작 노드로 돌아왔는지를 확인해야 한다.
• “이중 연결리스트가 무조건 더 좋다”고 단정하는 오류: 이중 연결리스트는 링크가 2개라 메모리를 더 쓰고, 삽입·삭제 시 갱신할 링크도 더 많다. 역방향 탐색이나 즉시 삭제가 필요 없다면 단순 연결리스트로 충분하다.

핵심 정리

• 이중 연결리스트는 prev·next 두 링크로 양방향 이동을 지원하며, 삭제할 노드를 알고 있으면 탐색 없이 바로 삭제할 수 있다.
• 이중 연결리스트의 삽입은 newNode의 prev·next, 그리고 양옆 노드의 링크까지 총 4개의 링크를 정확한 순서로 갱신해야 한다.
• 원형 연결리스트는 마지막 노드가 첫 노드를 다시 가리키며, 순회 종료는 NULL 대신 “시작 노드로 돌아왔는가”로 판단한다.
• 단순·이중·원형 연결리스트는 각각 링크 수, 역방향 이동 가능 여부, 메모리 사용량에서 트레이드오프를 가지며 상황에 맞게 선택한다.

마무리 복습

참고 자료

• 국가평생교육진흥원 과목별 평가영역  — 자료구조 과목의 범위와 평가영역을 확인할 수 있는 공식 안내.
• MDN JavaScript reference  — 참조 기반 자료구조와 컬렉션의 기본 개념을 확인할 수 있는 참고 자료.