C++で双方向リンクリストから偶数ノードをすべて削除する方法

このチュートリアルでは、C++を使って双方向リンクリスト（二重リンクリスト）から偶数のデータを持つノードをすべて削除する方法を解説します。

解決の手順

問題を解決するための流れは以下の通りです。

• データ（data）、前ポインタ（prev）、次ポインタ（next）を持つ構造体を定義します。
• 双方向リンクリストに新しいノードを挿入する関数を作成します。
• ダミーデータを使って双方向リンクリストを初期化します。
• リンクリストを走査し、現在のノードのデータが偶数かどうかを判定します。
• データが偶数であれば、そのノードを削除します。
• ノードを削除する関数を作成します。削除時には以下の3つの場合分けを考慮する必要があります。

• 先頭ノードの場合： ヘッドポインタを次のノードへ移動させます。
• 中間ノードの場合： 前のノードと次のノードを直接つなぎ合わせます。
• 末尾ノードの場合： 前のノードからのリンクを解除します。

サンプルコード

それでは、実際のコードを見てみましょう。

#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;
    }
    // 中間・末尾ノードの場合：次ノードのprevを更新
    if (del->next != NULL) {
        del->next->prev = del->prev;
    }
    // 中間・末尾ノードの場合：前ノードのnextを更新
    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);
}

実行結果

上記のプログラムを実行すると、以下のような出力が得られます。

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

ポイントの解説

このアルゴリズムで重要なのは、deleteEvenNodes 関数内でノードを削除する前に次のノードへのポインタを変数 next に保存しておく点です。ノードを削除するとそのメモリが解放されるため、削除後に temp->next にアクセスすると未定義動作を引き起こす可能性があります。

また、deleteNode 関数では先頭・中間・末尾の3パターンすべてに対応できるよう、ポインタの付け替えを慎重に行っています。これにより、どの位置のノードを削除してもリンクリストの整合性が保たれます。

まとめ

本チュートリアルでは、C++における双方向リンクリストから偶数ノードを削除する実装方法を学びました。ノード挿入、ノード削除、条件付き削除という一連の処理は、リンクリスト操作の基礎となる重要なテクニックです。チュートリアルについて質問がある場合は、コメント欄でお気軽にお尋ねください。