C++で単方向リンクリストの先頭にノードを挿入するプログラムの書き方

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

ここでは、与えられた単方向リンクリストの先頭（ヘッド）に新しいノードを挿入する方法を解説します。

入力例 − 1 → 2 → 3 → 4

このリンクリストの先頭に「5」を挿入します。

出力 − 5 → 1 → 2 → 3 → 4

説明 − 先頭にノードを挿入した後、リンクリストは 5 → 1 → 2 → 3 → 4 と表示されます。

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

最初に、複数のノードから構成されるリンクリストが与えられています。各ノードにはデータと次のノードへのアドレスが格納されています。

すでにノードが用意されているため、ヘッドノードのアドレスと挿入するデータを引数として受け取り、リンクリストの先頭にデータを挿入する関数を作成します。挿入後は、ヘッドポインタを新しく挿入したノードに向けるのがポイントです。

• 関数 insertAthead(node*&head, int data) は、ヘッドノードのアドレス（参照渡し）と挿入するデータを受け取ります。

• 新しいノードを作成し、そこにデータを格納します。

• 新しいノードのnextポインタを現在のヘッドに設定し、ヘッドを新しいノードに更新します。

• リンクリストを出力して結果を確認します。

コード例

#include<iostream>
using namespace std;
class node{
    public:
        int data;
        node* next;
        node(int d){
            data = d;
            next = NULL;
        }
};
void insertAthead(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;
    }
}
int main(){
    node* head = NULL;
    insertAthead(head, 5);
    insertAthead(head, 2);
    insertAthead(head, 8);
    insertAthead(head, 3);
    print(head);
}

出力

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

3→ 8→ 2→ 5 →

リンクリストの先頭にノード 3、8、2、5 を順番に挿入すると、出力は 3→ 8→ 2→ 5 → となります。先頭への挿入では最後に挿入したノードが常に先頭に来るため、挿入した順序と逆の順序で表示される点に注意してください。計算量は挿入1回あたりO(1)と非常に効率的です。