【C++】双方向リンクリストから指定した値より大きいノードをすべて削除する方法

このチュートリアルでは、C++を使って双方向リンクリスト( doubly linked list )から、指定された値より大きいデータを持つノードをすべて削除する方法を解説します。リンクリストの操作はデータ構造の基礎であり、ノードの挿入・削除のロジックを理解する絶好の題材です。

問題を解く手順

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

• データ本体(data)と前後へのポインタ(prev / next)を持つ構造体を定義します。

• 双方向リンクリストの先頭にノードを挿入する関数を作成します。

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

• リストを先頭から順に走査し、現在のノードのデータが指定値より大きいかどうかを判定します。

• 指定値より大きい場合は、そのノードを削除します。

• ノード削除用の関数を作成します。削除時には次の3つのケースを考慮する必要があります。

  • 先頭(ヘッド)ノードの場合：ヘッドポインタを次のノードへ移動させます。

  • 中間ノードの場合：前のノードと次のノードを直接つなぎます。

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

サンプルコード

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

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

コードのポイント

• deleteGreaterNode 関数:走査中にノードを削除するため、あらかじめ次のノードへのポインタ(next)を保存してから削除処理を行っています。これにより、削除後も安全に走査を続けられます。

• deleteNode 関数:削除対象が先頭・中間・末尾のどれでも対応できるよう、各ポインタの NULL チェックを行ってからリンクを付け替えています。

実行結果

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

Linked List before deletion:
12 -> 11 -> 10 -> 4 -> 3 -> 2 -> 1 ->
Linked List after deletion:
10 -> 4 -> 3 -> 2 -> 1 ->

K = 10 を指定したため、11 と 12 のみが削除され、残りのノードがそのまま保持されていることがわかります。

まとめ

このチュートリアルでは、双方向リンクリストから指定値より大きいノードをすべて削除する方法を学びました。重要なのは、削除前に次のノードへのポインタを退避させておくこと、そして先頭・中間・末尾の3パターンのリンク付け替えを正しく処理することです。このアルゴリズムの計算量は O(N)、空間計算量は O(1) となります。チュートリアルについて質問がある場合は、コメント欄でお気軽にお知らせください。