C++ 이중 연결 리스트에서 주어진 값보다 큰 모든 노드 삭제하기

이 튜토리얼에서는 C++을 사용해 이중 연결 리스트(Doubly Linked List)에서 주어진 값보다 큰 데이터를 가진 모든 노드를 삭제하는 방법을 알아봅니다.

문제 해결 접근 방식

아래 단계를 따라 문제를 해결할 수 있습니다.

• 정수형 데이터와 prev, next 포인터를 멤버로 가지는 구조체(struct)를 정의합니다.
• 이중 연결 리스트의 앞쪽에 새 노드를 삽입하는 함수를 작성합니다.
• 테스트용 더미 데이터로 이중 연결 리스트를 초기화합니다.
• 리스트를 처음부터 끝까지 순회하면서 현재 노드의 데이터가 주어진 값(K)보다 큰지 확인합니다.
• 조건을 만족하면 해당 노드를 삭제하고, 다음 노드로 이동해 같은 과정을 반복합니다.

노드 삭제 시 고려해야 할 세 가지 경우

노드를 안전하게 삭제하려면 노드의 위치에 따라 다음 세 가지 경우를 모두 처리해야 합니다.

• 헤드(첫 번째) 노드인 경우: 헤드 포인터를 다음 노드로 이동시킵니다.
• 중간 노드인 경우: 삭제할 노드의 다음 노드를 이전 노드에 연결합니다.
• 마지막 노드인 경우: 이전 노드의 next 포인터 연결을 제거합니다.

예제 코드

전체 코드를 살펴보겠습니다.

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

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

// 리스트 앞에 새 노드를 삽입하는 함수
void insertNode(Node** head_ref, int new_data) {
    Node* new_node = (Node*)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->prev = NULL;
    new_node->next = (*head_ref);
    if ((*head_ref) != NULL) {
        (*head_ref)->prev = new_node;
    }
    (*head_ref) = new_node;
}

// 특정 노드를 삭제하는 함수
void deleteNode(Node** head_ref, Node* del) {
    // 리스트가 비어 있거나 삭제할 노드가 없으면 종료
    if (*head_ref == NULL || del == NULL) {
        return;
    }
    // 삭제할 노드가 헤드 노드라면 헤드를 다음 노드로 이동
    if (*head_ref == del) {
        *head_ref = del->next;
    }
    // 중간 노드인 경우: 다음 노드를 이전 노드에 연결
    if (del->next != NULL) {
        del->next->prev = del->prev;
    }
    // 마지막 노드인 경우: 이전 노드의 next 연결 제거
    if (del->prev != NULL) {
        del->prev->next = del->next;
    }
    free(del);
    return;
}

// 값이 K보다 큰 모든 노드를 삭제하는 함수
void deleteGreaterNode(Node** head_ref, int K) {
    Node* temp = *head_ref;
    Node* next;
    while (temp != NULL) {
        next = temp->next; // 삭제 전에 다음 노드를 미리 저장
        if (temp->data > K) {
            deleteNode(head_ref, temp);
        }
        temp = next;
    }
}

// 연결 리스트 출력 함수
void printLinkedList(Node* head) {
    while (head != NULL) {
        cout << head->data << " -> ";
        head = head->next;
    }
}

int main() {
    Node* head = NULL;
    insertNode(&head, 1);
    insertNode(&head, 2);
    insertNode(&head, 3);
    insertNode(&head, 4);
    insertNode(&head, 10);
    insertNode(&head, 11);
    insertNode(&head, 12);

    int K = 10;

    cout << "Linked List before deletion:" << endl;
    printLinkedList(head);

    deleteGreaterNode(&head, K);

    cout << "
Linked List after deletion:" << endl;
    printLinkedList(head);
}

실행 결과

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.

Linked List before deletion:
12 -> 11 -> 10 -> 4 -> 3 -> 2 -> 1 ->
Linked List after deletion:
10 -> 4 -> 3 -> 2 -> 1 ->

K가 10으로 주어졌기 때문에 11과 12가 리스트에서 제거되고, 나머지 노드들은 그대로 유지됩니다.

마무리

이 문제의 핵심은 노드를 삭제하기 전에 다음 노드를 미리 저장해 두는 것입니다. 삭제 후에는 해당 노드에 더 이상 접근할 수 없기 때문에, 미리 저장하지 않으면 순회를 계속할 수 없습니다. 또한 헤드 노드, 중간 노드, 마지막 노드의 세 가지 경우를 모두 처리해야 메모리 누수나 댕글링 포인터 없이 안전하게 노드를 삭제할 수 있습니다.

튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.