C++ 이중 연결 리스트에서 잘못된 포인터 수정하는 방법

개요

이 글에서는 C++로 작성된 이중 연결 리스트(doubly linked list)에서 잘못 연결된 포인터를 찾아 수정하는 프로그램을 다룹니다.

정상적인 이중 연결 리스트에서는 각 노드의 next 포인터가 다음 노드를, prev 포인터가 이전 노드를 가리켜야 합니다. 그러나 문제가 된 리스트에는 하나의 노드가 인접하지 않은 노드를 가리키고 있으며, 우리의 목표는 이 잘못된 포인터를 찾아 올바른 대상, 즉 바로 옆에 있는 노드를 가리키도록 수정하는 것입니다.

알고리즘 접근 방식

리스트를 앞에서부터 순회하면서 모든 노드의 연결 관계를 검사합니다. 올바른 이중 연결 리스트라면 항상 다음 두 조건이 성립해야 합니다.

• node->next->prev == node : 다음 노드의 prev는 반드시 현재 노드를 가리켜야 합니다.
• node->prev->next == node : 이전 노드의 next는 반드시 현재 노드를 가리켜야 합니다.

순회 도중 이 조건이 깨진 노드를 발견하면 그곳이 바로 오류 지점입니다. 해당 포인터를 현재 노드를 가리키도록 수정한 뒤 탐색을 종료합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;

// 이중 연결 리스트의 노드 구조체
struct node {
    int data;
    node* next;
    node* prev;
};

// 새 노드 생성
node* newNode(int data){
    node* temp = new node;
    temp->data = data;
    temp->next = temp->prev = NULL;
    return temp;
}

// 잘못된 포인터 수정
void get_cpointer(node*& head){
    if (!head)
        return;
    node* temp = head;
    if (head->next && head->next->prev != head) {
        head->next->prev = head;
        return;
    }
    // 위치가 올바르지 않은 경우 수정
    if (head->prev != NULL) {
        head->prev = NULL;
        return;
    }
    temp = temp->next;
    while (temp) {
        if (temp->next && temp->next->prev != temp) {
            temp->next->prev = temp;
            return;
        }
        else if (temp->prev && temp->prev->next != temp) {
            temp->prev->next = temp;
            return;
        }
        temp = temp->next;
    }
}

// 이중 연결 리스트 출력
void printList(node* head) {
    node* temp = head;
    while (temp) {
        cout << temp->data << " (";
        cout << (temp->prev ? temp->prev->data : -1) << ") ";
        temp = temp->next;
    }
    cout << endl;
}

int main(){
    node* head = newNode(1);
    head->next = newNode(2);
    head->next->prev = head;
    head->next->next = newNode(3);
    head->next->next->prev = head;
    head->next->next->next = newNode(4);
    head->next->next->next->prev = head->next->next;
    cout << "\nIncorrect Linked List: ";
    printList(head);
    get_cpointer(head);
    cout << "\nCorrected Linked List: ";
    printList(head);
    return 0;
}

실행 결과

Incorrect Linked List: 1 (-1) 2 (1) 3 (1) 4 (3)
Corrected Linked List: 1 (-1) 2 (1) 3 (2) 4 (3)

결과 분석

출력에서 괄호 안의 숫자는 각 노드의 prev 포인터가 가리키는 노드의 데이터 값이며, 첫 번째 노드는 이전 노드가 없으므로 -1로 표시됩니다.

수정 전 결과를 보면 노드 3의 prev가 노드 1을 가리키고 있어 리스트의 연결이 손상된 상태였습니다. get_cpointer() 함수를 실행한 후에는 노드 3의 prev가 올바르게 노드 2를 가리키도록 수정된 것을 확인할 수 있습니다.

시간 및 공간 복잡도

• 시간 복잡도: O(n) — 리스트를 최대 한 번 순회합니다.
• 공간 복잡도: O(1) — 별도의 추가 메모리를 사용하지 않습니다.