データ構造（配列・リスト・スタック・キュー・マップ）

なぜ種類があるのか

データに対してやりたい操作は、ざっくり 検索・追加・削除・順番に走査 の4つ。ところが、これらすべてを同時に速くできる万能の入れ物はありません。

• 番号で一発アクセスしたい → 配列
• 途中への挿入・削除を頻繁にやりたい → 連結リスト
• 「最後に入れたものから取り出す」「最初に入れたものから取り出す」という順序が欲しい → スタック / キュー
• 「このキーに対応する値」を瞬時に引きたい → ハッシュマップ

だから用途に合わせて入れ物を選ぶ。これがデータ構造を学ぶ最大の理由です。なお、各操作の「速さ」は計算量（Big-O）で表します。本記事でも O(1) / O(n) などの記法を使うので、ピンと来ない場合は先にそちらを読むとスムーズです。

配列（Array）

メモリ上に要素を連続して並べる入れ物。先頭アドレス＋番号（インデックス）から「何バイト目」を即座に計算できるため、arr[5] のような添字アクセスが O(1) と非常に速いのが最大の強みです。

const arr = [10, 20, 30];
arr[1];          // 20  …… インデックス参照は O(1)
arr.push(40);    // 末尾追加は ならし O(1)
arr.unshift(5);  // 先頭追加は O(n)（後ろを全部ずらす）

弱点は途中の挿入・削除。間に1つ差し込むと、それ以降の要素を全部ずらす必要があり O(n) かかります。

連結リスト（Linked List）

各要素（ノード）が「値」と「次のノードへの参照」を持ち、数珠つなぎになった構造。メモリ上はバラバラの場所に置かれ、参照（ポインタ）でつながっています。

途中への挿入・削除は、前後のつなぎ替えだけで済むため O(1)（その位置を既に掴んでいる場合）。一方で「N番目」を知るには先頭から順にたどるしかなく、O(n) かかります。配列とちょうど裏返しの性能特性です。

[10] -> [20] -> [30] -> null
         ↑ ここに [15] を挿入 = 参照を2本つなぎ替えるだけ

スタックとキュー

どちらも「出し入れの順序にルールを設けた」入れ物です。中身は配列でも連結リストでも実装できますが、公開する操作を絞ることで用途を明確にします。

• スタック（Stack）: LIFO（Last In, First Out ＝ 後入れ先出し）。積み上げた皿のように、最後に置いたものから取る。push（積む）/ pop（取る）。
• キュー（Queue）: FIFO（First In, First Out ＝ 先入れ先出し）。行列のように、先に並んだ人から処理する。enqueue（並ぶ）/ dequeue（先頭を出す）。

// スタック（LIFO）
const stack = [];
stack.push('A'); stack.push('B');
stack.pop();      // 'B'（最後に入れたものが出る）

// キュー（FIFO）
const queue = [];
queue.push('A'); queue.push('B');
queue.shift();    // 'A'（最初に入れたものが出る）

マップ（ハッシュマップ）とセット

マップ（連想配列, 辞書）は「キー → 値」のペアを保存し、キーから値を引く入れ物。内部では ハッシュ関数でキーを配列上の位置に変換するため、検索・追加・削除がいずれも平均 O(1) という驚異的な速さです。

# Python の dict（ハッシュマップ）
prices = {"apple": 100, "banana": 80}
prices["apple"]            # 100 …… キー検索は平均 O(1)
prices["cherry"] = 300     # 追加も平均 O(1)
"banana" in prices         # 存在確認も平均 O(1)

**セット（Set）**は「キーだけ」のマップのようなもの。値の重複を許さない集合で、「すでに含まれているか」の判定が平均 O(1)。重複排除や「会員かどうか」の判定に向きます。

const seen = new Set();
seen.add(1); seen.add(1);  // 2回足しても
seen.size;                 // 1（重複は無視される）
seen.has(1);               // true …… 含有判定は平均 O(1)

計算量で見る早見表

代表的な操作の計算量を並べると、得意・不得意がはっきりします。

どう選ぶ？

• 番号で頻繁にアクセス／末尾に追加していく → 配列
• 先頭や途中での挿入・削除が多い（大きさが頻繁に変わる）→ 連結リスト
• 「直近のものから」処理したい（Undo、履歴）→ スタック
• 「来た順に」処理したい（待ち行列、順番待ち）→ キュー
• キーで一発検索したい／重複を排除したい → マップ・セット

迷ったら「この入れ物で一番よくやる操作は何か？」を自問してください。その操作が速い構造を選べば、たいてい正解です。実務では、まず汎用的な配列やマップで素直に書き、性能が問題になった箇所だけ最適な構造に置き換える――という進め方が現実的です。