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

このチュートリアルでは、C++を使って単方向連結リスト（Singly Linked List）から、データが素数であるノードをすべて削除する方法を解説します。

問題を解決する手順

• データと次ノードへのポインタを持つ構造体（struct）を定義します。
• 連結リストにノードを挿入する関数を作成します。
• ダミーデータで単方向連結リストを初期化します。
• 連結リストを走査し、現在のノードのデータが素数かどうかを判定します。
• 現在のデータが素数であれば、そのノードを削除します。
• ノードを削除する関数を作成します。削除時には以下の3つのケースを考慮する必要があります。
  • 先頭ノードの場合：ヘッドポインタを次のノードに移動します。
  • 中間ノードの場合：前のノードと次のノードを直接つなぎます。
  • 末尾ノードの場合：前のノードのリンクを解除します。

サンプルコード

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

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node *next;
};
void insertNode(Node** head_ref, int new_data) {
    Node* new_node = (Node*)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*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) {
    struct Node* temp = *head_ref;
    if (*head_ref == NULL || del == NULL) {
        return;
    }
    if (*head_ref == del) {
        *head_ref = del->next;
    }
    while (temp->next != del) {
        temp = temp->next;
    }
    temp->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 << "Linked List before deletion:" << endl;
    printLinkedList(head);
    deletePrimeNodes(&head);
    cout << "\nLinked List after deletion:" << endl;
    printLinkedList(head);
}

実行結果

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

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

処理のポイント

このプログラムでは、isPrime 関数が素数判定を行っています。6k±1 の最適化手法を用いることで、√n までの範囲を効率的にチェックできます。また、deletePrimeNodes 関数では、ノードを削除する前に次のノードへのポインタをあらかじめ保存しておくことで、リンク切れを防いで安全に走査を続けられるようにしています。

まとめ

本チュートリアルでは、単方向連結リストから素数ノードを削除する実装方法を学びました。ノード削除時には「先頭・中間・末尾」の3パターンそれぞれでリンクの張り替え方が異なる点が重要です。チュートリアルについて質問がある場合は、コメント欄でお気軽にお尋ねください。