<CodeLearn/>
アルゴリズム レッスン4

データ構造

配列、連結リスト、スタック、キュー、木、グラフの実装を学ぼう

連結リスト（Linked List）

各要素（ノード）がデータと次のノードへの参照を持つデータ構造です。 配列と違い、先頭への挿入・削除が O(1) で行えます。 ただし、インデックスアクセスは O(n) です。

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

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

  // 先頭に追加 O(1)
  prepend(value) {
    const node = new Node(value);
    node.next = this.head;
    this.head = node;
    this.size++;
  }

  // 末尾に追加 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++;
  }

  // 全要素を表示
  print() {
    const values = [];
    let current = this.head;
    while (current) {
      values.push(current.value);
      current = current.next;
    }
    console.log(values.join(" -> "));
  }
}

const list = new LinkedList();
list.append(1);
list.append(2);
list.append(3);
list.prepend(0);
list.print(); // 0 -> 1 -> 2 -> 3

スタック（Stack）

LIFO（Last In, First Out）の原則に従うデータ構造です。 最後に追加した要素が最初に取り出されます。 ブラウザの「戻る」ボタン、関数の呼び出し履歴、括弧の対応チェックなどに使われます。

class Stack {
  constructor() {
    this.items = [];
  }

  push(item) {
    this.items.push(item);  // O(1)
  }

  pop() {
    return this.items.pop(); // O(1)
  }

  peek() {
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  get size() {
    return this.items.length;
  }
}

// 括弧の対応チェック
function isValidParentheses(s) {
  const stack = new Stack();
  const pairs = { ")": "(", "]": "[", "}": "{" };

  for (const char of s) {
    if ("([{".includes(char)) {
      stack.push(char);
    } else {
      if (stack.pop() !== pairs[char]) return false;
    }
  }
  return stack.isEmpty();
}

console.log(isValidParentheses("({[]})")); // true
console.log(isValidParentheses("({)}"));   // false

キュー（Queue）

FIFO（First In, First Out）の原則に従うデータ構造です。 最初に追加した要素が最初に取り出されます。 タスクの処理順序、BFS、プリンタのジョブ管理などに使われます。

class Queue {
  constructor() {
    this.items = {};
    this.head = 0;
    this.tail = 0;
  }

  enqueue(item) {
    this.items[this.tail] = item;
    this.tail++;
  }

  dequeue() {
    if (this.isEmpty()) return undefined;
    const item = this.items[this.head];
    delete this.items[this.head];
    this.head++;
    return item;
  }

  peek() {
    return this.items[this.head];
  }

  isEmpty() {
    return this.tail - this.head === 0;
  }

  get size() {
    return this.tail - this.head;
  }
}

const q = new Queue();
q.enqueue("タスクA");
q.enqueue("タスクB");
q.enqueue("タスクC");
console.log(q.dequeue()); // "タスクA"（先に入れた方から）
console.log(q.dequeue()); // "タスクB"
console.log(q.size);      // 1

二分探索木（Binary Search Tree）

各ノードが最大2つの子ノードを持ち、左の子 < 親 < 右の子という規則を満たす木構造です。 探索・挿入・削除が平均 O(log n) で行えます。

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BST {
  constructor() {
    this.root = null;
  }

  insert(value) {
    const node = new TreeNode(value);
    if (!this.root) { this.root = node; return; }

    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (!current.left) { current.left = node; return; }
        current = current.left;
      } else {
        if (!current.right) { current.right = node; return; }
        current = current.right;
      }
    }
  }

  search(value) {
    let current = this.root;
    while (current) {
      if (value === current.value) return true;
      current = value < current.value ? current.left : current.right;
    }
    return false;
  }

  // 中間順走査（昇順で出力される）
  inOrder(node = this.root, result = []) {
    if (node) {
      this.inOrder(node.left, result);
      result.push(node.value);
      this.inOrder(node.right, result);
    }
    return result;
  }
}

const tree = new BST();
[8, 3, 10, 1, 6, 14].forEach(v => tree.insert(v));
console.log(tree.inOrder());    // [1, 3, 6, 8, 10, 14]
console.log(tree.search(6));    // true
console.log(tree.search(7));    // false

グラフ（Graph）

ノード（頂点）とエッジ（辺）で構成されるデータ構造です。 SNSの友人関係、路線図、Webページのリンクなど、もの同士の関係を表現するのに使います。

class Graph {
  constructor() {
    this.adjacencyList = {};
  }

  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) {
      this.adjacencyList[vertex] = [];
    }
  }

  // 無向グラフのエッジ追加
  addEdge(v1, v2) {
    this.adjacencyList[v1].push(v2);
    this.adjacencyList[v2].push(v1);
  }

  print() {
    for (const vertex in this.adjacencyList) {
      console.log(vertex, "->", this.adjacencyList[vertex].join(", "));
    }
  }
}

const g = new Graph();
["東京", "大阪", "名古屋", "福岡"].forEach(v => g.addVertex(v));
g.addEdge("東京", "大阪");
g.addEdge("東京", "名古屋");
g.addEdge("大阪", "福岡");
g.addEdge("名古屋", "大阪");
g.print();
// 東京 -> 大阪, 名古屋
// 大阪 -> 東京, 福岡, 名古屋
// 名古屋 -> 東京, 大阪
// 福岡 -> 大阪

まとめ

  • 連結リストは先頭への挿入・削除が O(1) だがインデックスアクセスは O(n)
  • スタック（LIFO）は関数呼び出し、元に戻す操作などに使われる
  • キュー（FIFO）はタスク管理、BFS などに使われる
  • 二分探索木は探索・挿入・削除が平均 O(log n)
  • グラフは関係性の表現に強く、BFS/DFS で探索できる
  • 問題に最適なデータ構造を選ぶことでアルゴリズムの効率が大幅に変わる
← 前のレッスン

探索アルゴリズム

次のレッスン →

アルゴリズム総合演習