C++で単方向リンクリストを実装する方法【サンプルコード付きで解説】

単方向リンクリスト（Singly Linked List）は、自己参照構造体を使って作成されたノード群から構成されるデータ構造の一種です。各ノードは「データ」と「次のノードへの参照（ポインタ）」という2つの要素で構成されています。リンクリスト全体へアクセスするために必要なのは、先頭ノードへの参照のみです。この先頭ノードは「ヘッド（head）」と呼ばれます。また、リストの末尾のノードは次のノードを持たないため、参照部分にはNULLが格納されます。

ここでは、C++で単方向リンクリストを実装するサンプルプログラムを紹介します。

サンプルコード

#include <iostream>
using namespace std;
struct Node {
    int data;
    struct Node *next;
};
struct Node* head = NULL;
void insert(int new_data) {
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = head;
    head = new_node;
}
void display() {
    struct Node* ptr;
    ptr = head;
    while (ptr != NULL) {
        cout<< ptr->data <<" ";
        ptr = ptr->next;
    }
}
int main() {
    insert(3);
    insert(1);
    insert(7);
    insert(2);
    insert(9);
    cout<<"The linked list is: ";
    display();
    return 0;
}

実行結果

The linked list is: 9 2 7 1 3

実行結果では、挿入した順序とは逆の「9 2 7 1 3」が表示されます。これは、insert()関数が常にリストの先頭に新しいノードを挿入するためです。最後に挿入した「9」が先頭に来ることになります。

コードの解説

1. Node構造体の定義

上記のプログラムでは、構造体Nodeがリンクリストの1つのノードを表しています。この構造体は、データ本体を格納するint型のdataと、次のノードを指すポインタnextを持っています。

struct Node {
    int data;
    struct Node *next;
};

2. insert()関数：先頭へのデータ挿入

insert()関数は、リンクリストの先頭に新しいデータを挿入します。処理の流れは以下のとおりです。

• malloc()を使って新しいノードnew_nodeのメモリを確保する
• new_nodeのdataフィールドに挿入したい値を格納する
• new_nodeのnextポインタを現在のheadに向ける
• headをnew_nodeに更新し、新しいノードをリストの先頭にする

void insert(int new_data) {
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = head;
    head = new_node;
}

なお、C++ではmalloc()の代わりにnew Nodeを使うこともできます。その場合、明示的なキャストが不要になり、よりC++らしい記述になります。

3. display()関数：リスト全体の表示

display()関数は、リンクリストの全ノードを先頭から順に表示します。まずポインタptrをheadに設定し、その後、ptrがNULLになる（＝末尾に到達する）まで、ptrを次のノードへ進めながら各ノードのdataを出力していきます。

void display() {
    struct Node* ptr;
    ptr = head;
    while (ptr != NULL) {
        cout<< ptr->data <<" ";
        ptr = ptr->next;
    }
}

4. main()関数：データの挿入と表示

main()関数では、まずinsert()関数を複数回呼び出してリンクリストに値を挿入し、その後display()関数を呼び出してリストの内容を表示しています。

int main() {
    insert(3);
    insert(1);
    insert(7);
    insert(2);
    insert(9);
    cout<<"The linked list is: ";
    display();
    return 0;
}

計算量のポイント

この実装では、先頭への挿入は既存ノードをたどる必要がないためO(1)で実行できます。一方、display()による全ノードの走査はノード数Nに比例してO(N)の計算量となります。単方向リンクリストは、挿入・削除を頻繁に行う場面で特に有効なデータ構造です。