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

片方向連結リストが与えられ、そこから末尾のノードを削除するのが本記事のテーマです。この問題は、与えられたリストを先頭から順に走査し、最後のノードを取り除くだけで解決できます。

解決のためのアプローチ

このアプローチでは、リストを走査しながら「直前のノード（prev）」と「現在のノード（curr）」を常に追跡します。そして、現在のノードが末尾ノードに到達した時点で、prev->next を NULL に設定し、curr のメモリを解放します。

実装例

#include <iostream>
using namespace std;

struct Node {
    int data;
    struct Node* next;
};
void push(struct Node** ref, int new_data) { // ノードを先頭に挿入
    struct Node* new_n = new Node;
    new_n->data = new_data;
    new_n->next = (*ref);
    (*ref) = new_n;
}
int main() {
    Node* head = NULL;
    push(&head, 12);
    push(&head, 29);
    push(&head, 11);
    push(&head, 23);
    push(&head, 8);
    auto curr = head, prev = head;
    if (!curr || !curr -> next) // リストが空、または要素が1つだけの場合
        cout << "Empty\n";
    else {
        while (curr) { // curr != NULL の間ループ
            if (!curr -> next) {
                prev -> next = NULL;
                delete(curr); // メモリを解放
                break;
            }
            prev = curr;
            curr = curr -> next; // 次のノードへ移動
        }
    }
    for (Node* temp = head; temp != NULL; temp = temp->next) // データを出力
        cout << temp->data << " ";

    return 0;
}

出力結果

8 23 11 29

コードの解説

このプログラムでは、リストを先頭から順に走査し、常に「直前のノード」と「現在のノード」を記録しています。現在のノードが末尾に到達したら、直前のノードの next ポインタを NULL に書き換え、delete を呼び出してメモリを解放します。なお、リストが空である場合やノードが1つしかない場合は特別な処理が必要となるため、最初にチェックを行っています。このプログラム全体の計算量は O(N) です。ここで N はリスト内のノード数を表します。

時間計算量 − O(N)

N：リスト内のノード数

まとめ

本記事では、与えられた連結リストから末尾のノードを削除する問題を解説しました。C++での具体的な実装例に加え、その考え方と処理の手順についても詳しく紹介しました。同じロジックは C、Java、Python など他のプログラミング言語でも同様に実装できます。この記事が皆さんの学習のお役に立てば幸いです。