連結リスト

連結リストとは

連結リスト (Linked List) は、各要素 (ノード) が値と次のノードへのポインタを持つ線形データ構造である。配列と異なりメモリ上で連続している必要がなく、先頭・末尾への挿入・削除が 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) が動的配列として実装されており、ほとんどのケースで配列の方が高速だ。連結リストが有利なのは、先頭への頻繁な挿入・削除が必要な場合に限られる。コーディング面接では頻出のデータ構造。

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