データ構造 — 配列・スタック・キュー・ハッシュテーブル

「このデータ、ListでいいのかMapでいいのか迷う」「push より unshift の方が自然だけど、遅いって聞いたことがある気がする」。データ構造は、ただ選ぶだけで性能が桁違いに変わる 要素です。

この章では、どの言語にも共通して出てくる5つの基本的なデータ構造を、「何が得意で、何が苦手か」 という視点で押さえます。

配列 — インデックスで一発アクセス

配列（Array） は、同じ種類のデータをメモリ上に連続して並べた 最も基本的なデータ構造です。

連続しているので、インデックスから物理的なメモリ位置を計算で一発で出せます。arr[3] は「先頭アドレス + 3 × 要素サイズ」という単純な計算で即座に取れるため、アクセスは O(1) です。

一方、途中に要素を挿入・削除するのは遅い（O(n)）です。たとえば [0] の位置に新しい要素を入れたければ、後ろの全要素を1つずつずらさないといけません。

JavaScriptの Array.unshift が push より遅いのはこれが理由です。先頭の出し入れが多いなら、配列ではなく後述のキュー系データ構造を検討 します。

スタック — 最後に入れたものを最初に取り出す (LIFO)

スタック は、Last In, First Out (LIFO) という規則で動くデータ構造です。お皿を積み上げて、一番上から順に取るイメージです。

操作は基本の2つだけです。

• push — 一番上に積む
• pop — 一番上から取る

スタックが一番ありふれた形で使われているのは、関数の呼び出し履歴を管理するコールスタック です。

function a() { b(); }
function b() { c(); }
function c() { throw new Error('boom'); }
 
a();
// Error: boom
//   at c (...)  ← c が最上位
//   at b (...)
//   at a (...)  ← a が一番下

エラーのスタックトレースを上から読めば「今どこにいるか」、下から読めば「どう呼ばれてきたか」が分かります。ブラウザの戻るボタンやエディタの Undo 機能も、内部的にはスタックです。

キュー — 最初に入れたものを最初に取り出す (FIFO)

キュー は、First In, First Out (FIFO)、並んだ順にサービスを受ける行列のイメージです。

Web開発では、非同期処理の順序管理 でよく顔を出します。

• ブラウザの タスクキュー（setTimeout のコールバックなどが並ぶ）
• ジョブキュー（Sidekiq、BullMQ、SQS など）
• メッセージキュー（RabbitMQ、Kafka など）

「とりあえず受け付けて、裏でゆっくり処理する」系のアーキテクチャは、ほぼキューで実現されています。

連結リスト — ポインタで繋がれたデータ

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

連結リストの強みは、途中の挿入・削除がO(1) であることです。配列のように後続をずらす必要がなく、ポインタをつなぎ替えるだけで済みます。

ただし、実務のWeb開発で自前で連結リストを実装することはほぼありません。LRUキャッシュや、ブラウザの履歴のようにノード間の挿入・削除が多いケース で言語の標準ライブラリが内部的に使っている、という理解で十分です。

ハッシュテーブル — キーで一発アクセス

ハッシュテーブル は、キーと値のペア を格納するデータ構造です。JavaScriptの Object や Map、Pythonの dict、Rubyの Hash、Goの map など、ほぼ全ての言語に組み込まれている 最重要データ構造です。

仕組みは単純で、キーを ハッシュ関数 に通して、データを置くインデックスを計算します。

キーの検索・挿入・削除は平均 O(1)。これが、あらゆる場面でハッシュテーブルが重宝される理由です。

衝突（コリジョン）

異なるキーが同じハッシュ値 になることがあります。これを 衝突 と呼びます。

解決方法は主に2つあります。

• チェイニング — 同じインデックスに連結リストでぶら下げる
• オープンアドレス法 — 衝突したら別の空き場所を探す

衝突が多くなると検索のたびにリストを辿ることになり、平均O(1)が最悪O(n) まで劣化します。

よくあるハマりどころ

1. JavaScriptで Array.shift をループの中で大量に使って遅い

shift（先頭を取り出す）は O(n)。キュー的に使いたいときは、代わりに Array.push と末尾からの pop を組み合わせるか、両端キューライブラリを使うべきです。

2. ハッシュテーブルのキーに使うオブジェクトが壊れる

JavaScriptで Map のキーにオブジェクトを使うと、参照で比較される ので「同じ中身だけど別インスタンス」は別キー扱いになります。文字列キーに正規化するか、意図した上で使う必要があります。

3. 「計算量O(1)」を盲信してDBキャッシュをメモリに全部載せる

ハッシュテーブルはCPU命令としては速いですが、データ量が物理メモリを超えると一気に遅くなる（前章のスワップ）どころかOOMで落ちます。O(1) はあくまで「項目数が増えても遅くならない」という意味です。

ちゃんと使うためのポイント

• 配列はインデックスアクセスO(1)、先頭の出し入れは避ける
• スタック(LIFO) はコールスタック・Undo 履歴、キュー(FIFO) はジョブキュー・タスクキュー
• 連結リスト は自前実装より、標準ライブラリの挙動を理解する用途が大半
• ハッシュテーブル は平均O(1)で最重要。衝突すると性能劣化することは覚えておく
• 「どのデータ構造を選ぶか」はどの操作を速くしたいかで決まる

次の章では、これらのデータ構造をどう処理するか という話、アルゴリズムと計算量 に進みます。O(n²) と O(n log n) の違いが、実務でどれくらい効いてくるかを掴みましょう。