お疲れ様です！ 
前回は「暗号化とハッシュ」を扱いました。今回は少し戻って、コンピュータサイエンスの土台 データ構造 の総まとめです。
というのも、これまでの「DFS / BFS」「計算量（Big-O）」「DBインデックス」——実はこの3記事、全部 データ構造 の話をしていました。
- DFS/BFS → スタックとキュー
- 計算量 → データ構造ごとの O(1) / O(n) / O(log n)
- インデックス → B-tree
今回はこれらを一枚の地図にまとめます。「データ構造ってアルゴリズムの授業のやつでしょ？」と思いきや、Railsを書いている時点で毎日全部使っています 👇
まず全体マップ：覚えるのは「得意・不得意」
データ構造は暗記モノではなく、「何が速くて、何が遅いか」のトレードオフ表 です。
| データ構造 | 特徴 | 計算量の目安 |
|---|---|---|
| 配列（Array） | 連続メモリ。インデックスアクセスが速い | アクセス O(1)、先頭への挿入・削除 O(n) |
| リンクトリスト | ポインタで連結。先頭・末尾の挿入削除が速い | アクセス O(n)、挿入・削除 O(1) |
| スタック | LIFO（後入れ先出し） | push / pop O(1) |
| キュー | FIFO（先入れ先出し） | enqueue / dequeue O(1) |
| ハッシュテーブル | キーから直接アクセス | 平均 O(1) |
| 木（Tree） | 親子関係を持つ階層構造 | 種類による（探索木なら O(log n)） |
| グラフ | ノードとエッジの集合 | 表現方法による |
「配列とリンクトリストは得意分野が真逆」 がまず最初のポイント。アクセスが速い配列 vs 挿入削除が速いリンクトリスト、です。
配列 vs リンクトリスト：なぜ真逆になるのか
配列： [ A | B | C | D ] ← メモリ上に連続で並ぶ
↑ 先頭アドレス + n×サイズ で一発計算 → アクセス O(1) 🙆
ただし先頭に挿入すると全員1つずつ後ろにズレる → O(n) 😤
リンクトリスト： A → B → C → D ← 各要素が「次はこっち」のポインタを持つ
↑ 3番目が欲しければ先頭からたどるしかない → アクセス O(n) 😤
ただし挿入はポインタを繋ぎ替えるだけ → O(1) 🙆
RubyのArrayは（内部実装的には動的配列なので）この「配列」側です。ary[3] が速くて、ary.unshift が遅い理由がまさにこれ。
ary = (1..1_000_000).to_a
ary[999_999] # O(1)：即答
ary.unshift(0) # O(n)：100万件が全部1つズレる 💥
ary.push(0) # 末尾追加はO(1)（償却）
スタックとキュー：Railsのどこにいる？
DFS / BFSの記事で出てきたコンビです。「取り出す順番」だけが違う シンプルな構造ですが、いる場所が超メジャーです。
| 構造 | 順番 | Railsでの居場所 |
|---|---|---|
| スタック（LIFO） | 後入れ先出し | コールスタック（例外の backtrace はスタックそのもの）、Rackの ミドルウェアスタック |
| キュー（FIFO） | 先入れ先出し | Sidekiq / ActiveJob のジョブキュー、コネクションプールの待ち行列 |
# スタック：メソッド呼び出しは積んで、戻る時に降ろす（だからback"trace"）
# キュー：先に enqueue したジョブから実行される
SomeJob.perform_later(user.id) # ← Redisのキューに enqueue（FIFO）
rails middlewareで出てくるあの一覧も「スタック」と呼ばれていますね。リクエストは上から下へ、レスポンスは下から上へ戻る、まさに後入れ先出しです。
ハッシュテーブル：Railsで一番働いている構造 🔑
キーからハッシュ値を計算して、格納場所へ直接ジャンプ する構造。だから平均 O(1)。
"user_id" ──ハッシュ関数──> 42番の箱 ──> 直接アクセス（探し回らない）🙆
RubyのHashそのもので、Railsでは空気のように使われています。
params[:user_id] # ← ハッシュテーブル
session[:current_user] # ← ハッシュテーブル
Rails.cache.read("key") # ← キャッシュストアも本質はkey-value（ハッシュ）
セット（Set） も仲間です。「重複を許さないコレクション」で、内部的にはハッシュテーブルで実装されることが多い。ary.include? の O(n) を O(1) にしたい時の定番です。
require 'set'
allowed = Set.new(%w[admin editor viewer])
allowed.include?(role) # 平均O(1)。配列のinclude?はO(n)
木（Tree）：バリエーションが多いので系譜で覚える 🌳
木は「親子関係を持つノードの集合」。種類が多く見えますが、系譜 で見ると1本道です。
二分木（子が最大2つ）
└ 二分探索木 BST（左 < 親 < 右 のルール追加 → 検索が平均O(log n)に）
└ 平衡二分探索木（AVL木・赤黒木：偏りを自動修正 → 最悪でもO(log n)保証）
└ B-tree（1ノードに複数キー → DBインデックスの主役）👑
- BST：ルールのおかげで「大小比較しながら降りる」だけで検索できる。ただし偏ると実質リンクトリスト（O(n)）に劣化 💥
- 平衡木：その劣化を防ぐため、挿入のたびに自動で回転して高さを保つ
-
B-tree：インデックスの記事で出てきたやつです。PostgreSQLやMySQLの
add_indexの中身はこれ。系譜の終着点がRailsに直結します
ほかに2つ、覚えておきたい木があります。
- トライ木（Trie）：文字列の前方一致検索に特化した木。1文字ずつ枝を降りていく構造で、Railsのルーティングエンジン（Journey）もURLのマッチングに木構造を使っています
- ヒープ（Heap）：「親は必ず子より小さい（or 大きい）」だけを保証するゆるい木。最小値（最大値）を常にO(1)で取り出せるので、優先度付きキューの実装に使われます
グラフ：木の親分
ノードとエッジ（辺）の集合。木は「閉路がない」「親が1つ」という制約付きグラフなので、グラフはその一般形です。
- SNSのフォロー関係、地図の経路探索、Bundlerのgem依存解決 などがグラフ問題
- 表現方法は 隣接リスト（各ノードが繋がり先リストを持つ）と 隣接行列（N×Nの表）の2つ
- たどり方が BFS / DFS。前々回の記事がそのまま使えます
# 隣接リスト表現はRubyだと「Hash + Array」で書ける（＝今日の内容の合わせ技）
graph = {
"A" => ["B", "C"],
"B" => ["D"],
"C" => ["D"],
"D" => []
}
応用：組み合わせると強い（LRUキャッシュ）💪
実務で問われるのは、単体よりも 組み合わせ です。代表例が LRUキャッシュ（Least Recently Used：容量が溢れたら「最近使っていないもの」から捨てるキャッシュ）。
要件を分解すると、1つの構造では足りないことがわかります。
要件①「キーで一発アクセスしたい」 → ハッシュテーブル（O(1)）
要件②「使った順を管理して、末尾を捨てたい」→ 双方向リンクトリスト（付け替えO(1)）
ハッシュだけ → 順序管理ができない 😤
リストだけ → キー検索がO(n) 😤
両方持つ → どちらの操作もO(1) 🙆
実はRubyのHashは 挿入順を保持する（内部でこの合わせ技相当をやっている）ので、LRUをかなり素直に書けます：
class LruCache
def initialize(capacity) = (@cap, @h = capacity, {})
def get(key)
return nil unless @h.key?(key)
@h[key] = @h.delete(key) # 消して入れ直す＝「最近使った」扱いで末尾へ
end
def put(key, value)
@h.delete(key)
@h[key] = value
@h.shift if @h.size > @cap # 先頭＝一番使ってないやつを捨てる
end
end
Rails.cache のMemoryStoreが容量オーバー時に古いエントリから捨てていくのも、この考え方の仲間です。「単体の得意技を知っているから、組み合わせが設計できる」——今日の表が効いてくるのはここです。
最後に
- データ構造は暗記ではなく トレードオフ表。「配列＝アクセスO(1)・挿入O(n)、リンクトリストは真逆」から覚える
- スタック＝コールスタック、キュー＝Sidekiq、ハッシュ＝params、B-tree＝add_index。Railsを書いていれば全部毎日触っています
- 木は「二分木 → BST → 平衡木 → B-tree」の系譜で覚えると、DBインデックスまで1本道でつながる
迷ったらまず 「その操作、O(1)でできる構造はどれ？」 と自問すると、選ぶべきデータ構造が自然に決まります 🙆