1.3データ構造

アルゴリズムの効率は、どのデータ構造を選ぶかでほぼ決まると言っても過言ではありません。同じ「複数の値を管理する」という目的でも、頻繁に行う操作（末尾追加なのか、途中挿入なのか、検索なのか）によって最適な構造は変わります。この節では代表的なデータ構造それぞれの得意・不得意を、具体的な操作の性質から理解します。

1.3.1配列とリスト

• 配列＝同じ型の要素を連続したメモリ領域に並べたデータ構造。添字（インデックス）を使えば任意の要素へO(1)（一定時間）でアクセスできる一方、途中への挿入・削除は後続要素をずらす必要がありコストが高い。
• リスト（連結リスト）＝各要素（ノード）が値と「次のノードへの参照」を持つデータ構造。途中への挿入・削除は参照の付け替えだけでO(1)だが、n番目の要素へのアクセスは先頭からたどる必要がありO(n)かかる。

1.3.2スタックとキュー

• スタック＝LIFO（Last In, First Out・後入れ先出し）の構造。最後に入れた要素が最初に取り出される。主な操作は push（積む）・pop（取り出す）。関数呼び出しの管理（コールスタック）、ブラウザの「戻る」履歴、構文解析の括弧対応チェックなどに使われる。
• キュー＝FIFO（First In, First Out・先入れ先出し）の構造。最初に入れた要素が最初に取り出される。主な操作は enqueue（追加）・dequeue（取り出し）。印刷ジョブの順番待ち、タスクの順次処理、幅優先探索（BFS）などに使われる。

1.3.3木構造・ハッシュ・グラフ

• 木構造＝1つの根（ルート）から枝分かれして広がる階層構造。各要素をノード、ノード間のつながりをエッジと呼ぶ。ファイルシステムの階層、組織図などが代表例。
• 2分木＝各ノードが最大2つの子ノード（左の子・右の子）しか持たない木構造。特に2分探索木は「左の子＜親＜右の子」という順序を保つことで、探索・挿入・削除が平均O(log n)で行える。
• ハッシュ＝キーをハッシュ関数で固定長の値（ハッシュ値）に変換し、その値を添字として配列に格納する仕組み。理想条件下では検索・挿入が平均O(1)と非常に高速だが、異なるキーが同じハッシュ値になる衝突への対処（チェイン法・オープンアドレス法等）が必要。
• グラフ＝ノード（頂点）とエッジ（辺）で「モノとモノの関係」を表す最も一般的な構造。木構造は「閉路（ループ）を持たないグラフ」の特殊形と位置づけられる。SNSの友人関係、路線図、Webページのリンク構造などが代表例。

あるWebアプリで「元に戻す（Undo）」機能を実装する場面を考えます。ユーザーの操作を時系列に記録し、Undoが呼ばれるたびに直近の操作だけを取り消したい——これはまさにスタック（LIFO）が最適な用途です。操作のたびに push で履歴を積み、Undo時に pop すれば、常に「最後に行った操作」から順に取り消せます。一方、同じアプリでバックグラウンドの画像変換ジョブを複数受け付け、受け付けた順番どおりに処理したいなら、これはキュー（FIFO）が適しています。ジョブ受付時に enqueue、ワーカーが処理を始めるときに dequeue すれば、先着順の処理が保証されます。次に、ユーザーIDから会員情報を高速に引く仕組みを設計する場合、IDをキーとしたハッシュテーブルを使えば平均O(1)で検索でき、配列を先頭から線形に探すよりはるかに高速です。ただし、異なるIDが同じハッシュ値になる衝突が起きうるため、衝突時の対処（同じバケットに複数件を連結して保持する等）を設計に含める必要があります。最後に、組織内の「誰が誰の上司か」という関係を表現したい場合、上下関係が明確で1人の直属上司しか持たない（＝閉路がない）なら木構造で表現でき、逆に「誰が誰をフォローしているか」のような相互に絡み合う関係（片方向でも循環しうる）を表したいなら、より一般的なグラフが必要になります。このように、要件（操作の順序性・検索速度・関係の形）を見極めることが、データ構造選定の本質です。

1.3.4この節のまとめ

• スタック＝LIFO（Undo等）、キュー＝FIFO（順番待ち等）。配列＝アクセスO(1)/挿入O(n)、リスト＝挿入O(1)/アクセスO(n)
• 2分探索木＝左<親<右の順序で平均O(log n)の検索。ハッシュ＝平均O(1)だが衝突対策が必要
• 木構造はグラフの特殊形（閉路なし）。グラフは一般的な関係（相互・循環を含む）を表す