【C++入門】連結リストから交互のノードを削除する方法

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

解決までの手順

全体の流れは以下の通りです。

• データ（data）と次ノードへのポインタ（next）を持つ構造体を定義する
• 単方向連結リストにノードを挿入する関数を作成する
• ダミーデータで連結リストを初期化する
• 連結リストを先頭から順に走査する
• 直前のノード（prev）を保持しながら、交互のノードを削除していく

ノード削除時に考慮すべき3つのケース

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

• 先頭ノードの場合：headポインタを次のノードへ移動させる
• 中間ノードの場合：次のノードを直前のノードに連結する
• 末尾ノードの場合：直前のノードからのリンクを解除する

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

サンプルコード

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

実行結果

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

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

アルゴリズムのポイント

この実装では、ポインタ prev が残しておきたいノードを指し、その直後のノード node を削除対象として扱います。prev->next = node->next によって削除対象ノードをリストから切り離し、free() でメモリを解放した後、prev を次の残存ノードへ進めて同様の処理を繰り返します。

リストの長さを n とすると、時間計算量は O(n)、追加で必要なメモリは O(1) と非常に効率的です。

まとめ

今回は、単方向連結リストから交互のノードを削除する方法を学びました。ポインタ操作の理解を深めるのに最適な題材なので、ぜひご自身でもコードを書いて試してみてください。チュートリアルの内容について質問や不明な点がある場合は、コメント欄でお気軽にお知らせください。