C++で単一連結リストから末尾ノード（テールノード）を削除する方法

連結リスト（リンクリスト）とは、線形データ構造の一種であり、複数の「ノード」で構成されます。各ノードには2つのフィールドがあり、1つは格納する値（データ）、もう1つは次のノードのアドレスを保持するためのポインタです。

本記事の課題は、連結リストの末尾からノードを削除することです。連結リストの最後にあるノードは「テールノード（末尾ノード）」と呼ばれます。なお、連結リストが空の場合はNULLを返します。

入出力例

入力1： 1 → 2 → 3 → 4 → 5
出力： 1 → 2 → 3 → 4 →
説明： 与えられた単一連結リストの末尾にあるノードは「5」です。最後のノードを削除すると、出力は 1 → 2 → 3 → 4 → となります。

入力2： 5 → 8 → 3
出力： 5 → 8 →
説明： 与えられた単一連結リストの末尾にあるノードは「3」です。末尾のノードを削除すると、出力は 5 → 8 → となります。

問題の解決アプローチ

この問題を解くシンプルな方法は、「前のノード（previous）」を表すポインタを用意し、現在のポインタ（current）が連結リストの最後のノードを指した時点で、その直前のノード情報を保持しておくというものです。

具体的には、連結リストの全ノードを順に走査し、現在のノードが末尾ノードに到達したかどうかを確認しながら進めます。そして最後に、末尾ノードを削除した連結リストを返します。

アルゴリズムの手順

• ノードを挿入して連結リストを初期化します。
• 関数 insertAtFirst(node*&head, int data) により、すべてのノードを連結リストの先頭に挿入します。
• 関数 deleteAtTail(node*head) は、先頭（head）を指すポインタを受け取ります。
• previous ノード用のポインタを作成し、NULLで初期化します。
• head を指す一時的なノードポインタ（temp）を作成します。
• temp ポインタが連結リストの末尾に到達するまで走査を続けます。
• 走査中、各ステップで temp の値を previous ポインタに保存します。
• 末尾に到達したら、temp ポインタが指すノードを削除（delete）します。
• previous ノードの next を NULL に設定して完了です。

C++実装例

#include<iostream>
using namespace std;
class node{
    public:
    int data;
    node*next;
    node(int d){
        data=d;
        node*next= NULL;
    }
};
void insertAtFirst(node*&head, int data){
    node*n= new node(data);
    n->next= head;
    head=n;
}
void printNode(node*head){
    while(head!=NULL){
        cout<<head->data<<"->";
        head=head->next;
    }
    cout<<endl;
}
void deleteatTail(node*head){
    node*prev= NULL;
    node*temp= head;
    while(temp->next!=NULL){
        prev= temp;
        temp=temp->next;
    }
    delete temp;
    prev->next= NULL;
    return;
}
int main(){
    node*head= NULL;
    insertAtFirst(head,5);
    insertAtFirst(head,4);
    insertAtFirst(head,3);
    insertAtFirst(head,2);
    insertAtFirst(head,1);
    deleteatTail(head);
    printNode(head);
}

実行結果

上記のコードを実行すると、以下の出力が得られます。

1→2→3→4→

コードの解説

入力として与えられた単一連結リストは 1 → 2 → 3 → 4 → 5 であり、この連結リストの末尾ノードは「5」です。deleteatTail 関数では、temp ポインタが next == NULL となる（＝末尾である）までループを回し、その間 previous ポインタに直前のノードを記録していきます。末尾ノードを delete で解放した後、previous ノードの next を NULL に設定することで、新しい末尾として正しく連結リストが更新されます。その結果、削除後の連結リストは 1 → 2 → 3 → 4 → となります。