連結リスト

連結リストとは

連結リスト (Linked List) は、各要素 (ノード) が値と次のノードへのポインタを持つ線形データ構造である。配列と異なりメモリ上で連続している必要がなく、先頭への挿入・削除は要素数によらず O(1) で行える。末尾も末尾ポインタを持たせれば追加は O(1) だが、単方向リストの末尾削除は直前のノードを先頭から辿り直すため O(n) になる (双方向リストなら O(1))。

配列との比較

配列との主な違いを以下に比較する。

操作	配列	連結リスト
インデックスアクセス	O(1)	O(n)
先頭への挿入	O(n)	O(1)
末尾への挿入	償却 O(1) (動的配列)	O(1) (末尾ポインタあり)
中間への挿入	O(n)	O(1) (直前のノードを持っている場合)
検索	O(n)	O(n)
メモリ	連続、キャッシュ効率が高い	分散、ポインタのオーバーヘッド

種類

連結リストには、ポインタの持ち方によって 3 つの代表的なバリエーションがある。

単方向: [A] → [B] → [C] → null

双方向: null ← [A] ⇄ [B] ⇄ [C] → null

循環: [A] → [B] → [C] → [A] (先頭に戻る)

TypeScript での実装

単方向連結リストの基本操作を TypeScript で実装すると次のようになる。

class ListNode<T> {
  constructor(public value: T, public next: ListNode<T> | null = null) {}
}

class LinkedList<T> {
  private head: ListNode<T> | null = null;

  prepend(value: T) {
    this.head = new ListNode(value, this.head);
  }

  find(value: T): ListNode<T> | null {
    let current = this.head;
    while (current) {
      if (current.value === value) return current;
      current = current.next;
    }
    return null;
  }

  toArray(): T[] {
    const result: T[] = [];
    let current = this.head;
    while (current) {
      result.push(current.value);
      current = current.next;
    }
    return result;
  }
}

実際の利用場面

代表的な利用場面を以下にまとめる。

場面	理由
LRU キャッシュ	双方向リスト + ハッシュマップで O(1) の挿入・削除
ブラウザの履歴	前へ/次へのナビゲーション (双方向リスト)
Undo/Redo	操作履歴の管理
メモリアロケータ	フリーリスト (空きメモリブロックの管理)

現代の開発での位置づけ

JavaScript/TypeScript では配列 (Array) が動的配列として実装されており、ほとんどのケースで配列の方が高速だ。計算量の表だけを見ると連結リストが有利に見えるが、実機での速さを決めるのはキャッシュである。配列は要素が連続して並ぶので、1 つ読むと同じキャッシュラインに載った後続の要素までまとめて CPU キャッシュへ入る。連結リストはノードごとにポインタを辿り、飛び先がメモリ上に散っているためキャッシュミスを繰り返す。ノードごとにポインタ分のメモリも余分に消費する。連結リストが有利なのは、先頭付近への挿入・削除が頻繁で、かつ操作する位置のノード参照を手元に持てる場合に限られる。コーディング面接では頻出のデータ構造なので、実装を手で書けるようにしておく価値はある。

より深く学ぶには関連書籍が役立つ。