C++で双方向連結リストから素数ノードをすべて削除する方法

このチュートリアルでは、C++を使って双方向連結リスト（ダブルリンクリスト）から、値が素数であるノードをすべて削除する方法を解説します。ノードの挿入、素数判定、そして安全なノード削除といった、連結リスト操作の基本が詰まった内容です。

アルゴリズムの手順

問題は以下の手順で解決できます。

• data・prev・next を持つ Node 構造体を定義する

• 双方向連結リストの先頭にノードを挿入する関数を作成する

• ダミーデータで双方向連結リストを初期化する

• リストを先頭から順に走査し、各ノードの値が素数かどうかを判定する

• 素数であれば、そのノードを削除する

ノード削除時の3つのケース

ノードを削除する関数では、削除対象の位置に応じて次の3つのケースを考慮する必要があります。

• 先頭ノードの場合：head ポインタを次のノードへ移動させる

• 中間ノードの場合：前のノードと次のノードを直接つなぎ替える

• 末尾ノードの場合：直前のノードの 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;
}
bool isPrime(int n) {
    if (n <= 1) {
        return false;
    }
    if (n <= 3) {
        return true;
    }
    if (n % 2 == 0 || n % 3 == 0) {
        return false;
    }
    for (int i = 5; i * i <= n; i = i + 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}
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 deletePrimeNodes(Node** head_ref) {
    Node* temp = *head_ref;
    Node* next;
    while (temp != NULL) {
        next = temp->next;
        if (isPrime(temp->data)) {
            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 << "削除前の連結リスト:" << endl;
    printLinkedList(head);
    deletePrimeNodes(&head);
    cout << "\n削除後の連結リスト:" << endl;
    printLinkedList(head);
}

コードのポイント

各関数の役割を簡単に整理しておきましょう。

• insertNode：リストの先頭に新しいノードを挿入します。先頭への挿入を繰り返すため、最終的なリストは入力順と逆になります。

• isPrime：素数判定を行う関数です。「6k±1」の性質を利用して √n までの範囲だけを調べることで、効率的に判定できます。

• deleteNode：指定したノードをリストから切り離して解放します。先頭・中間・末尾のどの位置でも正しく動作します。

• deletePrimeNodes：リスト全体を走査し、素数ノードを見つけたら削除します。削除前に次ノードへのポインタを保存しておくのが重要なポイントです。これを怠ると、ノード解放後に不正なメモリへアクセスしてしまいます。

なお、本コードでは malloc/free を使用していますが、C++ では new/delete を使うのが一般的です。

実行結果

上記のコードを実行すると、次のような出力が得られます。

削除前の連結リスト:
6 -> 5 -> 4 -> 3 -> 2 -> 1 ->
削除後の連結リスト:
6 -> 4 -> 1 ->

初期データは 1〜6 ですが、insertNode が先頭への挿入を行うため「6 → 5 → 4 → 3 → 2 → 1」の順で表示されます。このうち素数は 2・3・5 なので、削除後には「6 → 4 → 1」だけが残ります。

計算量

ノード数を n、ノードの最大値を m とすると、全体の時間計算量は O(n·√m) となります。これは、各ノードに対して O(√m) の素数判定を行いながら、リスト全体を O(n) で走査するためです。空間計算量は O(1) です。

まとめ

本記事では、双方向連結リストから素数ノードをすべて削除する C++ の実装方法を学びました。ポイントは、削除前に次ノードへのポインタを退避することと、先頭・中間・末尾の3ケースに応じてリンクを正しく張り替えることの2つです。チュートリアルの内容についてご不明な点があれば、コメント欄でお気軽にお尋ねください。