Day 2: 配列と連結リスト

今日学ぶこと

• 配列の仕組みと操作の計算量
• 連結リストの仕組みと実装
• 単方向・双方向連結リストの違い
• 配列と連結リストの使い分け

---

配列（Array）

配列は、メモリ上に連続した領域にデータを格納するデータ構造です。インデックスを使って任意の位置に瞬時にアクセスできます。

flowchart LR
    subgraph Array["配列（メモリ上の連続領域）"]
        A0["[0]\n42"]
        A1["[1]\n17"]
        A2["[2]\n93"]
        A3["[3]\n8"]
        A4["[4]\n56"]
    end
    style Array fill:#3b82f6,color:#fff

配列の基本操作

// Create an array
const arr = [42, 17, 93, 8, 56];

// Access by index: O(1)
console.log(arr[2]); // 93

// Search for a value: O(n)
console.log(arr.indexOf(93)); // 2

// Add to end: O(1) amortized
arr.push(71);

// Add to beginning: O(n) - all elements must shift
arr.unshift(0);

// Remove from end: O(1)
arr.pop();

// Remove from beginning: O(n)
arr.shift();

// Insert at middle: O(n)
arr.splice(2, 0, 99);

配列の計算量

操作	計算量	理由
インデックスアクセス	O(1)	メモリアドレスの直接計算
末尾に追加	O(1)*	末尾のアドレスは既知
先頭に追加	O(n)	全要素をシフト
中間に挿入	O(n)	挿入位置以降をシフト
値の検索	O(n)	先頭から順に比較
末尾の削除	O(1)	末尾のアドレスは既知
先頭の削除	O(n)	全要素をシフト

*償却計算量（amortized）：配列の拡張が必要な場合はO(n)

---

連結リスト（Linked List）

連結リストは、各要素（ノード）がデータと次のノードへの**ポインタ（参照）**を持つデータ構造です。メモリ上に連続している必要はありません。

flowchart LR
    H["Head"] --> N1["42\nnext →"]
    N1 --> N2["17\nnext →"]
    N2 --> N3["93\nnext →"]
    N3 --> N4["8\nnext →"]
    N4 --> NULL["null"]
    style H fill:#f59e0b,color:#fff
    style N1 fill:#3b82f6,color:#fff
    style N2 fill:#3b82f6,color:#fff
    style N3 fill:#3b82f6,color:#fff
    style N4 fill:#3b82f6,color:#fff

単方向連結リストの実装

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

class LinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }

  // Add to beginning: O(1)
  prepend(value) {
    const node = new Node(value);
    node.next = this.head;
    this.head = node;
    this.size++;
  }

  // Add to end: O(n)
  append(value) {
    const node = new Node(value);
    if (!this.head) {
      this.head = node;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }
    this.size++;
  }

  // Remove from beginning: O(1)
  removeFirst() {
    if (!this.head) return null;
    const value = this.head.value;
    this.head = this.head.next;
    this.size--;
    return value;
  }

  // Search: O(n)
  find(value) {
    let current = this.head;
    while (current) {
      if (current.value === value) return current;
      current = current.next;
    }
    return null;
  }

  // Insert at position: O(n) to find position, O(1) to insert
  insertAt(index, value) {
    if (index === 0) return this.prepend(value);
    const node = new Node(value);
    let current = this.head;
    for (let i = 0; i < index - 1 && current; i++) {
      current = current.next;
    }
    if (!current) return;
    node.next = current.next;
    current.next = node;
    this.size++;
  }

  // Convert to array for display
  toArray() {
    const result = [];
    let current = this.head;
    while (current) {
      result.push(current.value);
      current = current.next;
    }
    return result;
  }
}

// Usage
const list = new LinkedList();
list.prepend(3);
list.prepend(2);
list.prepend(1);
list.append(4);
console.log(list.toArray()); // [1, 2, 3, 4]

---

双方向連結リスト

双方向連結リストでは、各ノードが前のノードへの参照も持ちます。これにより、末尾からの操作も O(1) で行えます。

flowchart LR
    H["Head"] --> N1
    N1["← 42 →"] <--> N2["← 17 →"]
    N2 <--> N3["← 93 →"]
    N3 --> T["Tail"]
    style H fill:#f59e0b,color:#fff
    style T fill:#f59e0b,color:#fff
    style N1 fill:#8b5cf6,color:#fff
    style N2 fill:#8b5cf6,color:#fff
    style N3 fill:#8b5cf6,color:#fff

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

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  // Add to end: O(1)
  append(value) {
    const node = new DoublyNode(value);
    if (!this.tail) {
      this.head = node;
      this.tail = node;
    } else {
      node.prev = this.tail;
      this.tail.next = node;
      this.tail = node;
    }
    this.size++;
  }

  // Add to beginning: O(1)
  prepend(value) {
    const node = new DoublyNode(value);
    if (!this.head) {
      this.head = node;
      this.tail = node;
    } else {
      node.next = this.head;
      this.head.prev = node;
      this.head = node;
    }
    this.size++;
  }

  // Remove from end: O(1)
  removeLast() {
    if (!this.tail) return null;
    const value = this.tail.value;
    if (this.head === this.tail) {
      this.head = null;
      this.tail = null;
    } else {
      this.tail = this.tail.prev;
      this.tail.next = null;
    }
    this.size--;
    return value;
  }

  // Remove specific node: O(1) if node reference is known
  removeNode(node) {
    if (node.prev) node.prev.next = node.next;
    else this.head = node.next;

    if (node.next) node.next.prev = node.prev;
    else this.tail = node.prev;

    this.size--;
    return node.value;
  }
}

---

配列 vs 連結リスト

flowchart TB
    subgraph Compare["どちらを選ぶ？"]
        Q1{"ランダムアクセス\nが必要？"}
        Q2{"先頭への挿入/削除\nが頻繁？"}
        Q3{"メモリ効率\n重視？"}
    end
    Q1 -->|Yes| Array["配列"]
    Q1 -->|No| Q2
    Q2 -->|Yes| LL["連結リスト"]
    Q2 -->|No| Q3
    Q3 -->|Yes| Array
    Q3 -->|No| LL
    style Compare fill:#3b82f6,color:#fff
    style Array fill:#22c55e,color:#fff
    style LL fill:#8b5cf6,color:#fff

操作	配列	連結リスト
インデックスアクセス	O(1)	O(n)
先頭への挿入	O(n)	O(1)
末尾への挿入	O(1)※	O(n) / O(1)※※
中間への挿入	O(n)	O(n)※※※
値の検索	O(n)	O(n)
メモリ使用	効率的	ポインタ分のオーバーヘッド
キャッシュ効率	高い	低い

※ 償却計算量　※※ tail参照がある場合　※※※ 位置が既知なら O(1)

---

実践例：LRUキャッシュ

配列と連結リストを組み合わせた実践的なデータ構造の例として、LRU（Least Recently Used）キャッシュがあります。

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map(); // O(1) lookup
    this.list = new DoublyLinkedList(); // O(1) reorder
  }

  get(key) {
    if (!this.map.has(key)) return -1;
    const node = this.map.get(key);
    // Move to front (most recently used)
    this.list.removeNode(node);
    this.list.prepend(node.value);
    this.map.set(key, this.list.head);
    return node.value.val;
  }

  put(key, value) {
    if (this.map.has(key)) {
      this.list.removeNode(this.map.get(key));
    }
    this.list.prepend({ key, val: value });
    this.map.set(key, this.list.head);

    if (this.map.size > this.capacity) {
      const removed = this.list.removeLast();
      this.map.delete(removed.key);
    }
  }
}

---

まとめ

概念	説明
配列	連続したメモリに格納、インデックスでO(1)アクセス
連結リスト	ノードがポインタで繋がる、先頭操作がO(1)
双方向連結リスト	前後の参照を持ち、両端からO(1)操作可能
キャッシュ効率	配列はCPUキャッシュに有利

重要ポイント

1. 配列はランダムアクセスが高速、連結リストは挿入・削除が高速
2. JavaScriptのArrayは動的配列で、内部的にメモリを自動拡張する
3. 双方向連結リストは両端からの操作が効率的
4. 実際のアプリケーションでは両方を組み合わせて使うことが多い

---

練習問題

問題1: 基本

連結リストを逆順にする関数を実装してください。

function reverseList(head) {
  // Your implementation here
}

問題2: 応用

連結リストの中央のノードを返す関数を実装してください（ヒント：2つのポインタを使う）。

チャレンジ問題

2つのソート済み連結リストを1つのソート済み連結リストにマージする関数を実装してください。

---

参考リンク

• MDN - Array
• Wikipedia - Linked list
• LeetCode - Linked List Problems

---

次回予告: Day 3では「スタックとキュー」について学びます。LIFO（後入れ先出し）とFIFO（先入れ先出し）の概念を理解しましょう。