sko.kr

アルゴリズム - 10. 連結リスト

algorithmsdata-structureslinked-listpointersdynamic-memory
By sko•10/7/2025•6 min read

連結リストを使うタイミング

連結リストは、既知の位置での効率的な挿入・削除を伴う動的サイズが必要な場合に使用します。配列はランダムアクセスに優れていますが、連結リストは以下の場合に適しています：

  • 先頭での頻繁な挿入・削除（クラシックなユースケース）
  • スタックとキューの実装（O(1)の操作）
  • アンドゥ機能（操作履歴の維持）
  • 音楽プレイリスト（次へ・前へナビゲーション）
  • ブラウザ履歴（進む・戻るナビゲーション）
  • 頻繁に要素を追加・削除し、ランダムアクセスが不要な問題全般

例題

テキストエディタのアンドゥシステム：無制限のアンドゥ/リドゥ機能のために、すべての編集操作を追跡する必要があるテキストエディタを構築しています。

  • ユーザーが "Hello" と入力（5つの操作）
  • ユーザーが "lo" を削除（2つの操作）
  • ユーザーが " World" と入力（6つの操作）
  • ユーザーが最後の3つの操作をアンドゥしたい

解答：連結リストは操作のシーケンスを完璧に維持し、新しい操作のO(1)での挿入と、アンドゥ操作のための逆方向への簡単なトラバーサルを可能にします。配列とは異なり、使用しない可能性のあるスペースを事前に割り当ててメモリを無駄にしません。

最も重要な洞察

連結リストは、ランダムアクセスを犠牲にして、どこでもO(1)時間で挿入・削除できる能力を得ています - そして境界でダミーノードを使用することで、操作ポイントの前後に常にノードが存在するため、すべてのエッジケースを排除できます。

メンタルノート：連結リストの天才性は、そのポインタベースの接続にあります。各ノードは隣接ノードのみを知っており、チェーンを作成します。このローカルな知識により、わずかなポインタの更新だけでノードを挿入または削除できます - 要素のシフトは必要ありません。ダミーノードパターンは、nullのhead/tailを扱うことがないことを保証し、すべての操作を統一します。

意思決定フレームワーク

連結リストのすべての操作において、決定はポインタ操作に関するものです：

  • 挿入：新しいノードをチェーンに織り込むためにポインタを更新
  • 削除：ターゲットノードをバイパスするためにポインタを更新
  • トラバース：チェーンを一度に1ノードずつたどる
  • エッジケースの排除：統一された操作を保証するためにダミーノードを使用

コード

ダミーノードを使用した単方向連結リスト

// リストの各要素は、値と次へのポインタを持つ「ノード」
class ListNode {
  constructor(value) {
    this.value = value;
    this.next = null; // チェーンの次のノードを指す
  }
}

class LinkedList {
  constructor() {
    // ダミーヘッドは永続的な「開始」マーカーとして機能
    this.dummyHead = new ListNode("START");
    this.tail = this.dummyHead; // テールは最後のノードを追跡
  }

  // push: 末尾に追加（array.pushのように）
  push(value) {
    const newNode = new ListNode(value);

    // 意思決定フレームワーク：単純にテールに接続
    this.tail.next = newNode; // 現在の最後のノードが新しいノードを指す
    this.tail = newNode; // テールを新しい最後のノードに更新
  }

  // pop: 末尾から削除（array.popのように）
  pop() {
    // 意思決定フレームワーク：リストが空かチェック
    if (this.dummyHead.next === null) {
      return undefined;
    }

    // 最後から2番目のノードを見つける
    let current = this.dummyHead;
    while (current.next !== this.tail) {
      current = current.next;
    }

    // 返すために値を保存
    const poppedValue = this.tail.value;

    // 最後のノードを削除
    current.next = null;
    this.tail = current;

    return poppedValue;
  }

  // unshift: 先頭に追加（array.unshiftのように）
  unshift(value) {
    const newNode = new ListNode(value);

    // 意思決定フレームワーク：ダミーの直後に挿入
    const oldFirst = this.dummyHead.next;
    newNode.next = oldFirst; // 新しいノードが古い最初を指す
    this.dummyHead.next = newNode; // ダミーが新しいノードを指す

    // リストが空だった場合、テールを更新
    if (this.tail === this.dummyHead) {
      this.tail = newNode;
    }
  }

  // shift: 先頭から削除（array.shiftのように）
  shift() {
    // 意思決定フレームワーク：リストが空かチェック
    if (this.dummyHead.next === null) {
      return undefined;
    }

    const firstNode = this.dummyHead.next;
    const shiftedValue = firstNode.value;

    // 最初のノードをバイパス
    this.dummyHead.next = firstNode.next;

    // 唯一のノードを削除した場合、テールをリセット
    if (firstNode === this.tail) {
      this.tail = this.dummyHead;
    }

    return shiftedValue;
  }

  // ヘルパー：リスト内の内容を確認
  display() {
    const items = [];
    let current = this.dummyHead.next; // ダミーをスキップ

    while (current !== null) {
      items.push(current.value);
      current = current.next;
    }

    return items.join(" → ");
  }
}

// 例：タスクリストの管理
const todos = new LinkedList();

// 末尾にタスクを追加
todos.push("牛乳を買う");
todos.push("コードを書く");
todos.push("運動する");
console.log(todos.display()); // 牛乳を買う → コードを書く → 運動する

// 緊急タスクを先頭に追加
todos.unshift("母に電話する");
console.log(todos.display()); // 母に電話する → 牛乳を買う → コードを書く → 運動する

// 最初のタスクを完了
const completed = todos.shift();
console.log(`完了：${completed}`); // 完了：母に電話する
console.log(todos.display()); // 牛乳を買う → コードを書く → 運動する

// 最後のタスクを削除
const removed = todos.pop();
console.log(`削除：${removed}`); // 削除：運動する
console.log(todos.display()); // 牛乳を買う → コードを書く

デュアルダミーノードを使用した双方向連結リスト

// 各ノードは次と前の両方のノードへのポインタを持つ
class DoublyListNode {
  constructor(value) {
    this.value = value;
    this.next = null; // 前方を指す
    this.prev = null; // 後方を指す
  }
}

class DoublyLinkedList {
  constructor() {
    // 2つのダミーノードが永続的な「しおり」として機能
    this.dummyHead = new DoublyListNode("START");
    this.dummyTail = new DoublyListNode("END");

    // しおり同士を接続
    this.dummyHead.next = this.dummyTail;
    this.dummyTail.prev = this.dummyHead;
  }

  // push: 末尾に追加（array.pushのように）
  push(value) {
    const newNode = new DoublyListNode(value);

    // 意思決定フレームワーク：最後の実ノードとdummyTailの間に挿入
    const lastNode = this.dummyTail.prev;

    // 4つの接続をすべて配線
    newNode.prev = lastNode; // 新しいノードが最後に戻る
    newNode.next = this.dummyTail; // 新しいノードがダミーテールに進む
    lastNode.next = newNode; // 最後のノードが新しいに進む
    this.dummyTail.prev = newNode; // ダミーテールが新しいに戻る

    return this; // チェーンのため
  }

  // pop: 末尾から削除（array.popのように）
  pop() {
    // 意思決定フレームワーク：リストが空かチェック
    if (this.dummyHead.next === this.dummyTail) {
      return undefined;
    }

    const lastNode = this.dummyTail.prev;
    const secondToLast = lastNode.prev;
    const poppedValue = lastNode.value;

    // 最後のノードをバイパス
    secondToLast.next = this.dummyTail;
    this.dummyTail.prev = secondToLast;

    return poppedValue;
  }

  // unshift: 先頭に追加（array.unshiftのように）
  unshift(value) {
    const newNode = new DoublyListNode(value);

    // 意思決定フレームワーク：dummyHeadと最初の実ノードの間に挿入
    const firstNode = this.dummyHead.next;

    // 4つの接続をすべて配線
    newNode.prev = this.dummyHead; // 新しいノードがダミーヘッドに戻る
    newNode.next = firstNode; // 新しいノードが最初に進む
    this.dummyHead.next = newNode; // ダミーヘッドが新しいに進む
    firstNode.prev = newNode; // 最初のノードが新しいに戻る

    return this; // チェーンのため
  }

  // shift: 先頭から削除（array.shiftのように）
  shift() {
    // 意思決定フレームワーク：リストが空かチェック
    if (this.dummyHead.next === this.dummyTail) {
      return undefined;
    }

    const firstNode = this.dummyHead.next;
    const secondNode = firstNode.next;
    const shiftedValue = firstNode.value;

    // 最初のノードをバイパス
    this.dummyHead.next = secondNode;
    secondNode.prev = this.dummyHead;

    return shiftedValue;
  }

  // ヘルパー：リスト内の内容を確認
  display() {
    const items = [];
    let current = this.dummyHead.next;

    while (current !== this.dummyTail) {
      items.push(current.value);
      current = current.next;
    }

    return items.join(" ⟷ ");
  }

  // ボーナス：逆方向にナビゲート
  displayReverse() {
    const items = [];
    let current = this.dummyTail.prev;

    while (current !== this.dummyHead) {
      items.push(current.value);
      current = current.prev;
    }

    return items.join(" ⟷ ");
  }
}

// 例：次へ/前へ付きの音楽プレイリスト
const playlist = new DoublyLinkedList();

// 曲を追加
playlist.push("曲 A");
playlist.push("曲 B");
playlist.push("曲 C");
console.log(playlist.display()); // 曲 A ⟷ 曲 B ⟷ 曲 C

// 先頭に曲を追加
playlist.unshift("イントロの曲");
console.log(playlist.display()); // イントロの曲 ⟷ 曲 A ⟷ 曲 B ⟷ 曲 C

// 逆順で再生
console.log("逆順:", playlist.displayReverse()); // 曲 C ⟷ 曲 B ⟷ 曲 A ⟷ イントロの曲

// 最初の曲をスキップ
const skipped = playlist.shift();
console.log(`スキップ：${skipped}`); // スキップ：イントロの曲

// 最後の曲を削除
const removed = playlist.pop();
console.log(`削除：${removed}`); // 削除：曲 C

console.log(playlist.display()); // 曲 A ⟷ 曲 B

疑問の解消

よくある疑問：「配列の方がシンプルに見えるのに、なぜ連結リストを使うのですか？配列はインデックスで任意の要素に直接アクセスできます！」

これは適切なデータ構造を選択することに関する基本的な質問です。トレードオフを検証してみましょう。

配列が常に優れていると思う理由

配列の利点を考えてみましょう：

  • 「配列はインデックスでO(1)のランダムアクセスを提供」
  • 「配列はより良いキャッシュ局所性を持つ（要素が連続して格納される）」
  • 「ポインタ用の余分なメモリが不要」
  • 「よりシンプルなメンタルモデル - ただの連続ブロック」

この考え方が重要なシナリオを見逃す理由

重要な認識：配列には挿入と削除に隠れたコストがあります！

配列の中央に挿入する際に何が起こるかを追ってみましょう：

配列: [A, B, C, D, E]
インデックス2にXを挿入：

ステップ1: すべてを右にシフトしてスペースを作る
[A, B, _, C, D, E]  // Cがインデックス3に移動
[A, B, _, _, D, E]  // Dがインデックス4に移動
[A, B, _, _, _, E]  // Eがインデックス5に移動

ステップ2: Xを挿入
[A, B, X, C, D, E]

総操作数: 平均n/2回のシフト = O(n)

具体例：パフォーマンス比較

先頭に1000要素を挿入：

配列のアプローチ：

  • 1回目の挿入：0要素をシフト
  • 2回目の挿入：1要素をシフト
  • 3回目の挿入：2要素をシフト
  • ...
  • 1000回目の挿入：999要素をシフト
  • 総シフト数：0 + 1 + 2 + ... + 999 = 499,500回の操作！

連結リストのアプローチ：

  • すべての挿入：2つのポインタを更新
  • 総操作数：1000 × 2 = 2,000回の操作

連結リストでは250倍少ない操作です！

それぞれの構造が輝く時

配列を使う時：

  • ランダムアクセスが必要（arr[500]への直接アクセス）
  • データサイズが比較的固定
  • 主にデータを読み取る
  • キャッシュパフォーマンスが重要

連結リストを使う時：

  • 既知の位置での頻繁な挿入・削除
  • データサイズが大幅に変動
  • シーケンシャルなトラバースのみ
  • メモリが断片化している（連結リストは散在したメモリを使用可能）

ダミーノードが天才的な理由

ダミーノードがない場合、すべての操作でチェックが必要：

  • 「これは最初のノードか？」（ヘッドの特殊ケース）
  • 「これは最後のノードか？」（テールの特殊ケース）
  • 「リストは空か？」（どこでもnullチェック）

ダミーノードがある場合：

  • ターゲットの前には常にノードが存在（dummyHead）
  • ターゲットの後には常にノードが存在（双方向連結のdummyTail）
  • 空のリストでもダミー構造は存在
  • すべての操作が同じパターンを使用 - 特殊ケースなし！

保証：ダミーノードは、エッジケースだらけのデータ構造を、統一された操作を持つものに変換します。これは単なる便利さではありません - nullポインタエラーと特殊ケース処理の可能性を排除することで、バグのないコードを書くことです。

← Back to Blog