C++ 이중 연결 리스트에서 짝수 노드 모두 삭제하기

이 튜토리얼에서는 C++로 작성된 이중 연결 리스트(Doubly Linked List)에서 데이터가 짝수인 모든 노드를 삭제하는 방법을 알아보겠습니다.

문제를 해결하는 단계는 다음과 같습니다.

• 데이터(data)와 prev, next 포인터를 가지는 구조체(struct)를 정의합니다.

• 노드를 이중 연결 리스트에 삽입하는 함수를 작성합니다.

• 더미 데이터로 이중 연결 리스트를 초기화합니다.

• 이중 연결 리스트를 순회하면서 현재 노드의 데이터가 짝수인지 확인합니다.

• 현재 데이터가 짝수라면 해당 노드를 삭제합니다.

• 노드를 삭제하는 함수를 별도로 작성합니다. 노드 삭제 시에는 다음 세 가지 경우를 고려해야 합니다.

  • 헤드(머리) 노드인 경우: 헤드 포인터를 다음 노드로 이동시킵니다.

  • 중간 노드인 경우: 다음 노드를 이전 노드에 연결하여 리스트의 연결을 유지합니다.

  • 마지막(꼬리) 노드인 경우: 이전 노드의 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;
    }
    if (del->prev != NULL) {
        del->prev->next = del->next;
    }
    free(del);
    return;
}
void deleteEvenNodes(Node** head_ref) {
    Node* temp = *head_ref;
    Node* next;
    while (temp != NULL) {
        next = temp->next;
        if (temp->data % 2 == 0) {
            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, 5);
    insertNode(&head, 6);
    cout << "Linked List before deletion:" << endl;
    printLinkedList(head);
    deleteEvenNodes(&head);
    cout << "\nLinked List after deletion:" << endl;
    printLinkedList(head);
}

코드 설명

• insertNode: 새 노드를 리스트의 맨 앞에 삽입하는 함수입니다.

• deleteNode: 특정 노드를 안전하게 삭제하며, 헤드·중간·끝 위치에 따라 포인터를 적절히 재연결합니다.

• deleteEvenNodes: 리스트를 순회하면서 짝수 데이터를 가진 노드를 찾아 삭제합니다. 삭제 후에도 순회를 계속할 수 있도록 다음 노드 주소를 미리 저장해 두는 점이 핵심입니다.

실행 결과

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

Linked List before deletion:
6 -> 5 -> 4 -> 3 -> 2 -> 1 ->
Linked List after deletion:
5 -> 3 -> 1 ->

마무리

이번 튜토리얼에서는 이중 연결 리스트를 순회하며 짝수 노드만 골라 삭제하는 방법을 배웠습니다. 핵심은 노드를 삭제하기 전에 다음 노드의 주소를 미리 저장해 두는 것입니다. 이렇게 하면 노드가 삭제된 이후에도 안전하게 순회를 이어갈 수 있습니다.

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