C++で双方向リンクリストの指定位置にあるノードを削除する方法

このチュートリアルでは、C++を使って双方向リンクリスト(doubly linked list)から、指定された位置にあるノードを削除する方法を解説します。

問題を解くための手順

まずは、全体の流れを確認しましょう。

• データ本体と prev(前)・next(次)の2つのポインタを持つ構造体を定義します。
• 双方向リンクリストにノードを挿入する関数を作成します。
• ダミーデータを使ってリンクリストを初期化します。
• 削除対象となるノードの位置(position)を設定します。
• リンクリストを先頭から走査し、指定位置に該当するノードを見つけます。
• ノードを削除する関数を実装します。削除時には、以下の3つのケースを考慮する必要があります。

• 先頭ノードの場合: headポインタを次のノードへ移動させます。
• 中間ノードの場合: 前のノードと次のノード同士を直接連結します。
• 末尾ノードの場合: 前のノードからのリンクを解除します。

実装例

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

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    struct Node *prev, *next;
};

// 指定ノードを削除する関数
void deleteNode(struct Node** head_ref, struct 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);
}

// 指定位置のノードを削除する関数
void deleteNodeAtGivenPosition(struct Node** head_ref, int n) {
    if (*head_ref == NULL || n <= 0) {
        return;
    }
    struct Node* current = *head_ref;
    // n番目のノードまで移動
    for (int i = 1; current != NULL && i < n; i++) {
        current = current->next;
    }
    if (current == NULL) {
        return;
    }
    deleteNode(head_ref, current);
}

// リンクリストの先頭にノードを挿入する関数
void insertNode(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct 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;
}

// リンクリストを表示する関数
void printLinkedList(struct Node* head) {
    while (head != NULL) {
        cout << head->data << "->";
        head = head->next;
    }
}

int main() {
    struct Node* head = NULL;
    insertNode(&head, 5);
    insertNode(&head, 2);
    insertNode(&head, 4);
    insertNode(&head, 8);
    insertNode(&head, 10);

    cout << "削除前の双方向リンクリスト" << endl;
    printLinkedList(head);

    int n = 2;
    deleteNodeAtGivenPosition(&head, n);

    cout << "\n削除後の双方向リンクリスト" << endl;
    printLinkedList(head);

    return 0;
}

実行結果

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

削除前の双方向リンクリスト
10->8->4->2->5->
削除後の双方向リンクリスト
10->4->2->5->

コードのポイント

このプログラムでは、insertNode関数が常にリストの先頭に新しいノードを挿入するため、挿入順序とは逆の「10→8→4→2→5」という並びになります。位置 n = 2 を指定して削除すると、2番目のノードである「8」が取り除かれ、「10→4→2→5」という結果になります。

削除処理では、del->next や del->prev がNULLかどうかを必ずチェックすることで、先頭・中間・末尾のどの位置のノードでも安全に削除できるようになっています。

まとめ

本チュートリアルについて不明な点や質問がある場合は、コメント欄でお気軽にお知らせください。