C++で単方向リンクリストの先頭ノードを削除する方法を解説

リンクリスト（連結リスト）とは、複数のノードが相互に接続された線形データ構造のことです。各ノードは「データフィールド」と「次のノードのアドレス」という2つのフィールドで構成されています。

ここでは、単方向リンクリストから先頭ノードを削除する方法について考えてみましょう。まずは具体例を見ていきます。

入力1 − 4 → 3 → 2 → 1

出力 − 3 → 2 → 1 →

説明 − 「4」は与えられた単方向リンクリストの先頭ノードです。このノードを削除すると、リンクリストは 3 → 2 → 1 となります。

入力2 − 1 → 2 → 3 →

出力 − 2 → 3 →

説明 − 先頭ノード「1」を削除すると、リンクリストは 2 → 3 となります。

問題を解くためのアプローチ

まず、ノードで構成されるリンクリストを用意します。各ノードにはデータ本体と、次のノードへのアドレスが格納されています。リンクリストへのデータ挿入が完了したら、先頭ノードを削除するための関数を作成します。

具体的な手順は次のとおりです。最初にhead（先頭）を指す一時ポインタを作成し、続けてheadを次のノードへ移動させます。その後、不要になった一時ノードをdeleteで解放し、処理後のリンクリストを返します。

• 関数 deleteAtFirst(node*&head) はheadへのポインタを受け取り、リンクリストの先頭ノードを削除します。

• 最初にheadを指す一時ポインタを作成します。

• headを次のノードへ移動させます。

• 一時ポインタが指すメモリをdeleteで解放します。

• 処理後のリンクリストを返します。

コード例

#include<iostream>
using namespace std;

class node{
    public:
        int data;
        node* next;
        node(int d){
            data = d;
            next = NULL;
        }
};

void insertAtFirstNode(node*& head, int data){
    node* n = new node(data);
    n->next = head;
    head = n;
}

void print(node* head){
    while(head != NULL){
        cout << head->data << "->";
        head = head->next;
    }
    cout << endl;
}

void deleteAtFirst(node*& head){
    if(head == NULL){
        return;
    }
    node* temp = head;
    head = head->next;
    delete temp;
}

int main(){
    node* head = NULL;
    insertAtFirstNode(head, 1);
    insertAtFirstNode(head, 2);
    insertAtFirstNode(head, 3);
    insertAtFirstNode(head, 4);
    deleteAtFirst(head);
    print(head);
    return 0;
}

出力

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

3 → 2 → 1 →

与えられた単方向リンクリストが 4 → 3 → 2 → 1 → である場合、先頭ノードである「4」を削除すると、リンクリストは 3 → 2 → 1 → となります。このように、一時ポインタを使ってheadを次のノードに移すだけで、O(1)の計算量で先頭ノードを安全に削除できます。