単方向リンクリスト｜コードで実践

単方向リンクリスト

このレッスンで分かること

リンクリストの本質は「データ + 次のノードへの参照」を 1 つの ノード にまとめること

配列 (array) は「連続したメモリ領域」に値を並べるのに対し、リンクリスト (linked list) は 値と「次の要素への参照」をワンセットにした ノード を、ポインタでつないでいくデータ構造です

各 ノード は次の 2 つのフィールドを持ちます

単方向リンクリストとは

Node クラスを連結して 単方向リンクリスト を構築する。linkedListFromArray(values) で配列からリンクリストを作り、たどった値の配列を返す。

配列 (array) は「連続したメモリ領域」に値を並べるのに対し、リンクリスト (linked list) は 値と「次の要素への参照」をワンセットにした ノード を、ポインタでつないでいくデータ構造です。

リンクリストの本質は「データ + 次のノードへの参照」を 1 つの ノード にまとめること。

リンクリストの構造

各 ノード は次の 2 つのフィールドを持ちます。

value — 格納する値
next — 次の ノード への参照 (末尾なら None / null)

diagram (will load when visible)

図のポイント (テキスト併記)

Node 1 の next は Node 2 を指し、最後の Node 3 の next だけが null になります

Node 1 の next は Node 2 を指し、最後の Node 3 の next だけが null になります。この「末尾の next は null」というルールが、リンクリスト の終端判定を支えます。

配列との違い

操作	配列	リンクリスト
インデックスでアクセス	O(1)	O(n)
先頭への挿入	O(n)	O(1)
末尾への挿入	O(1) (amortized)	O(n) (tail を持てば O(1))

配列 は連続領域なのでランダムアクセスは速い反面、先頭への挿入で全要素をずらす必要があります。リンクリスト は要素同士がメモリ上で離れていてもよく、挿入・削除は next を付け替えるだけ。

Node クラス

OOP の練習として、Node を クラス で定義します。

Python

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

たった 2 つの属性で、リンクリスト の ノード として機能します。

配列からリンクリストを構築 + traverse

配列 [10, 20, 30] を リンクリスト に変換するには、先頭ノードを作り、current ポインタを使って 1 個ずつ末尾に連結します。最後にもう一度 head からたどって値を集めれば完成です。

Python

def linkedListFromArray(values):
    if not values:
        return []
    head = Node(values[0])
    current = head
    for v in values[1:]:
        current.next = Node(v)
        current = current.next
    out = []
    cur = head
    while cur is not None:
        out.append(cur.value)
        cur = cur.next
    return out

current = current.next の 1 行が「ポインタを次のノードへ進める」操作です。while cur is not None のループが、リンクリスト をたどるときの基本パターン。

JavaScript での実装

JavaScript

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

function linkedListFromArray(values) {
  if (values.length === 0) return [];
  const head = new Node(values[0]);
  let current = head;
  for (let i = 1; i < values.length; i++) {
    current.next = new Node(values[i]);
    current = current.next;
  }
  const out = [];
  let cur = head;
  while (cur !== null) {
    out.push(cur.value);
    cur = cur.next;
  }
  return out;
}

よくある間違い

current = current.next の代入を忘れて、ずっと head を見続けて無限ループ。
空配列で values[0] を読みに行き、IndexError になる。if not values で先に弾く。
next を null で初期化せず、undefined になっていて末尾判定がうまくいかない。

リンクリストの応用

リンクリスト は単独で使うより、他の データ構造 の 内部実装 として使われることが多いです。

ハッシュテーブル の衝突処理 (チェイン法)
LRU キャッシュ で末尾要素を O(1) で取り出す双方向リンクリスト
グラフ の隣接リスト表現

やってみよう

関数 linkedListFromArray(values) を実装してください。values から Node を連結して リンクリスト を作り、もう一度先頭からたどって値を 配列 に集めて返します。空配列なら空配列を返してください。テストでは [10, 20, 30] → [10, 20, 30] のように同じ並びになることを確認します (内部はリンクリスト構造、戻り値は配列)。

よくある質問

Q. リンクリストと配列はどう使い分けますか？

A. 配列はランダムアクセス O(1)、リンクリストは先頭への追加 O(1) が強みです。ほとんどの実用ケースで配列の方が速く、リンクリストはアルゴリズム問題の練習や特殊用途（OS のスケジューラ等）で使われる程度です。

Q. サイクル検出はどう実装しますか？

A. Floyd の循環検出（2 ポインタ法、tortoise and hare）が定番です。slow を 1 ステップ、fast を 2 ステップ進めると、ループがあれば必ず同じノードで出会います。空間 O(1) で動くのが優秀な点です。

Q. リンクリストを反転するコツは？

A. prev, curr, next の 3 ポインタを使い、curr.next = prev で 1 個ずつ繋ぎ替えます。再帰版でも書けますが、反復版の方がスタック消費が無く安全です。LeetCode の Reverse Linked List が定型問題なので解いておくと良いです。

次のレッスン

次は 二分探索木 (BST) への挿入 で、二分探索木 (BST) への挿入を学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

リンクリストの要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. リンクリストとは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

単方向リンクリスト