C++でヘッドポインタなしに片方向連結リストからノードを削除する方法

このチュートリアルでは、片方向連結リスト（シングルリンクリスト）において、ヘッドポインタなしでノードを削除する方法を解説します。

通常、連結リストからノードを削除するには、削除対象ノードの直前のノードへのポインタが必要です。しかし、ヘッドポインタが渡されていない場合、前のノードをたどってたどり着くことができません。そこで役立つのが「次のノードのデータをコピーする」というテクニックです。

解決の手順

• データ（data）と次ノードへのポインタ（next）を持つ構造体を定義する
• 片方向連結リストにノードを挿入する関数を実装する
• ダミーデータを使って連結リストを初期化する
• nextポインタを使って、削除対象ノードへのポインタを取得する
• 削除対象ノードに次のノードのデータをコピーし、次のノードを削除する

アルゴリズムのポイント

ヘッドポインタがないため、削除対象ノードの前のノードを特定できません。そこで、ノード自体を削除する代わりに、次のノードのデータを削除対象ノードに上書きし、その後次のノードを解放（free）します。これにより、実質的に削除対象ノードが削除されたのと同じ状態になります。

なお、この手法には「末尾のノードは削除できない」という制限があります。末尾ノードには次のノードが存在しないため、コピー元がなく、ノードをリストから切り離すこともできないからです。

サンプルコード

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

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    struct Node* next;
};
void deleteNodeWithoutHead(struct Node* deletingNode) {
    if (deletingNode == NULL) {
        return;
    }
    else {
        if (deletingNode->next == NULL) {
            cout << "Can't delete last node without head" << endl;
            return;
        }
        struct Node* temp = deletingNode->next;
        deletingNode->data = temp->data;
        deletingNode->next = temp->next;
        free(temp);
    }
}
void printLinkedList(Node* head) {
    Node* temp = head;
    while (temp) {
        cout << temp->data << " -> ";
        temp = temp->next;
    }
}
void insertNode(struct Node** head_ref, int new_data) {
    struct Node* new_node = new Node();
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}
int main() {
    struct 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);
    Node* del = head->next;
    deleteNodeWithoutHead(del);
    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 -> 3 -> 2 -> 1 ->

この例では、先頭から2番目のノード（値が5のノード）を削除対象として渡しています。結果として、リストの先頭ノードの次にあった「5」が消え、「6 -> 4 -> 3 -> 2 -> 1」という連結リストになっていることが確認できます。

まとめ

ヘッドポインタなしでノードを削除するには、「次のノードのデータをコピーして、次のノードを削除する」という手法が有効です。計算量はO(1)と非常に効率的ですが、末尾ノードには適用できない点に注意しましょう。本チュートリアルについて質問がある場合は、コメント欄でお気軽にお知らせください。