IT 技書の森

連結リスト

各要素が次の要素へのポインタを持つ線形データ構造

データ構造アルゴリズム

連結リストとは

連結リスト (Linked List) は、各要素 (ノード) が値と次のノードへのポインタを持つ線形データ構造である。配列と異なりメモリ上で連続している必要がなく、先頭・末尾への挿入・削除が O(1) で行える。

配列との比較

操作 配列 連結リスト
インデックスアクセス O(1) O(n)
先頭への挿入 O(n) O(1)
末尾への挿入 O(1) (動的配列) O(1) (末尾ポインタあり)
中間への挿入 O(n) O(1) (位置が既知)
検索 O(n) O(n)
メモリ 連続、キャッシュ効率が高い 分散、ポインタのオーバーヘッド

種類

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

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

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

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 操作履歴の管理
メモリアロケータ フリーリスト (空きメモリブロックの管理)

LRU キャッシュ

// 双方向連結リスト + Map で O(1) の LRU キャッシュ
class LRUCache<K, V> {
  private map = new Map<K, V>();
  constructor(private capacity: number) {}

  get(key: K): V | undefined {
    if (!this.map.has(key)) return undefined;
    const value = this.map.get(key)!;
    this.map.delete(key);
    this.map.set(key, value); // 末尾に移動 (最近使用)
    return value;
  }

  set(key: K, value: V) {
    this.map.delete(key);
    this.map.set(key, value);
    if (this.map.size > this.capacity) {
      this.map.delete(this.map.keys().next().value!); // 先頭を削除 (最も古い)
    }
  }
}

現代の開発での位置づけ

JavaScript/TypeScript では配列 (Array) が動的配列として実装されており、ほとんどのケースで配列の方が高速だ。連結リストが有利なのは、先頭への頻繁な挿入・削除が必要な場合に限られる。コーディング面接では頻出のデータ構造。

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

関連用語