C++で双方向連結リストのノードを削除する方法

はじめに

このチュートリアルでは、C++における双方向連結リスト（Doubly Linked List）からノードを削除する方法を解説します。双方向連結リストは、各ノードが前後両方のノードへのポインタを持つデータ構造であり、削除処理を行う際には隣接ノード同士のリンクを正しく繋ぎ直すことが重要です。

解決の手順

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

• data、prev、nextポインタを持つ構造体を定義します。

• 双方向連結リストにノードを挿入する関数を記述します。

• ダミーデータを使って双方向連結リストを初期化します。

• 削除対象のノードを指定します。

• ノードを削除する関数を記述します。削除時には以下の3つのケースを考慮する必要があります。

  • ノードが先頭ノード（head）の場合：headを次のノードに移動します。

  • ノードが中間ノードの場合：次のノードと前のノードを相互にリンクし直します。

  • ノードが末尾ノードの場合：前のノードのnextリンクを解除します。

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

サンプルコード

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

出力結果

上記のプログラムを実行すると、以下の結果が得られます。

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

コードの解説

deleteNode関数では、まずheadまたは削除対象ノードがNULLの場合に何もせず処理を終了します。削除対象がheadノードであれば、headを次のノードへ更新します。その後、削除対象ノードの次のノードが存在する場合はそのprevポインタを、前のノードが存在する場合はそのnextポインタをそれぞれ更新することで、リンクリストから対象ノードを切り離します。最後にfree関数でメモリを解放して完了です。この実装により、先頭・中間・末尾のどの位置のノードでも共通のロジックで安全に削除できます。

まとめ

このチュートリアルでは、C++で双方向連結リストからノードを削除する方法を学びました。ご不明な点があれば、コメント欄でお気軽にお知らせください。