C++로 이중 연결 리스트에서 주어진 값보다 작은 노드 모두 삭제하는 방법

개요

이번 튜토리얼에서는 이중 연결 리스트(Doubly Linked List)에서 주어진 값보다 작은 데이터를 가진 노드를 모두 삭제하는 방법을 알아보겠습니다.

문제 해결 과정은 다음과 같습니다.

• 데이터(data)와 prev, next 포인터를 포함하는 구조체(struct)를 정의합니다.
• 이중 연결 리스트에 새 노드를 삽입하는 함수를 작성합니다.
• 테스트용 더미 데이터로 이중 연결 리스트를 초기화합니다.
• 리스트를 순회하면서 현재 노드의 데이터가 주어진 값보다 작은지 확인합니다.
• 현재 노드의 데이터가 기준값보다 작다면 해당 노드를 삭제합니다.

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

노드를 안전하게 삭제하려면 다음 상황들을 반드시 처리해야 합니다.

• 삭제할 노드가 헤드(head) 노드인 경우: head 포인터를 다음 노드로 이동시킵니다.
• 삭제할 노드가 중간 노드인 경우: 이전 노드와 다음 노드를 서로 연결하여 끊어진 부분을 이어줍니다.
• 삭제할 노드가 마지막(tail) 노드인 경우: 이전 노드의 next 링크를 제거(NULL 처리)합니다.

예제 코드

전체 구현 코드는 다음과 같습니다.

#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;
    }
    if (del->prev != NULL) {
        del->prev->next = del->next;
    }
    free(del);
    return;
}
void deleteSmallerNodes(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);
    deleteSmallerNodes(&head, K);
    cout << "\nLinked List after deletion:" << endl;
    printLinkedList(head);
}

실행 결과

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

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

동작 방식 설명

deleteSmallerNodes 함수에서 주목할 점은 순회 전에 미리 next 노드를 저장한다는 것입니다. 삭제 함수가 현재 노드를 제거하면 원래의 next 포인터에 접근할 수 없게 되기 때문입니다. 이처럼 next = temp->next; 코드를 먼저 실행해 두면, 노드가 삭제된 후에도 안전하게 다음 노드로 이동할 수 있습니다.

위 예제에서는 K=10으로 설정했기 때문에 4, 3, 2, 1 노드가 삭제되고 10 이상의 값(12, 11, 10)만 남게 됩니다.

마무리

이 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요. 도움이 되었기를 바랍니다!