1 データ構造の概要
データ構造とは、データを保存し、必要な操作を行う際の振る舞いを、ある形式として整理したものを指す。保存方法（どこにどう置くか）と操作方法（どう探し、どう更新するか）を組み合わせて考えることで、処理時間や必要メモリ量の見積もり、設計判断の根拠が得られる。
多くの場面では「目的に対して適切な構造を選ぶこと」が性能を左右する。例えば頻繁な探索が中心なら探索効率、順序付きでの更新が多いなら順序維持の仕組み、少ないメモリで扱う必要があるなら空間効率といった観点が重要になる。また、データ構造は理論上の計算量だけでなく、実装の複雑さ、バグりやすさ、保守性、計算機の実装特性（キャッシュ効率など）にも影響される。
1.1 抽象データ型（ADT）
抽象データ型（ADT）は、データの内容や操作の集合を定義しつつ、実装の詳細を隠す考え方である。利用者は「何ができるか」を知ればよく、「どのように内部で実現されるか」は要求されない。この分離により、アルゴリズムや仕様検討を進めやすくなる。
1.1.1 値と操作の分離
ADTの特徴は、対象となる値（格納されるデータ）と、それに対して実行可能な操作（取得、更新、削除など）を明確に区別する点にある。値の性質に対して操作がどう振る舞うかを定義することで、同じ仕様を満たす別実装が可能になる。結果として、後から性能特性を改善する置き換えがしやすくなる。
1.1.2 実装との関係
ADTは仕様であり、実装ではない。具体的な表現（配列、連結リスト、木、ハッシュ表など）は要求性能や制約に合わせて選ばれる。たとえば同じ「辞書」概念でも、探索頻度や順序要件により、木構造やハッシュ構造といった異なる実装が選択される。ADTに基づく設計では、外部から観測できる振る舞いを崩さずに内部表現を変更できるため、拡張や最適化の余地が残る。
1.2 計算量と評価指標
データ構造の選定では、処理コストを指標化する必要がある。代表的には時間計算量と空間計算量が用いられ、入力サイズに応じた増え方を比較する。評価は理論的な解析だけでなく、定数項やメモリ配置の違いも踏まえて行うのが実務上の要点になる。
1.2.1 時間計算量の考え方
時間計算量は、入力規模の増加に伴って操作の実行時間がどう増えるかを示す。典型例として、配列の末尾追加は一定時間で済む一方、先頭への挿入は要素移動を伴うため増加する、といった傾向がある。多くの場合、厳密な秒数ではなく漸近的な成長率を使って比較するが、現実の環境ではキャッシュヒット率や分岐予測などが定数項に効いてくる。
また、同じ操作でも「平均」と「最悪」の挙動が異なる場合がある。たとえばハッシュ表は平均的には高速でも、衝突が偏る状況では急激に遅くなり得る。この差を理解し、運用条件に照らして評価することが重要になる。
1.2.2 空間計算量とメモリ効率
空間計算量は、入力サイズに対する追加メモリ量の増え方を表す。要素そのものを格納する領域だけでなく、ポインタ、参照、補助配列、バッファなどのオーバーヘッドも含めて見積もる必要がある。特に木やグラフの表現では、参照構造や重みの保持が支配的になりやすい。
加えて、メモリ効率には「局所性」も関わる。連続領域にデータが置かれるほど参照時の待ち時間は減りやすい一方、分散した配置はキャッシュに不利になることがある。理論計算量が同等でも、実装が異なれば体感性能が変わるため、空間と時間を同時に考える姿勢が求められる。
1.3 設計上の選択基準
データ構造は「どれが常に最適か」で決まるものではなく、求める操作の種類と頻度、制約、運用の性質で最適解が変わる。選定では、アクセスのパターン、更新の性質、必要な順序、メモリ上限、実装・保守のコストといった要素を整理することが有効である。
1.3.1 アクセスパターンに基づく選定
アクセスパターンとは、どのような操作をどれくらい繰り返すかという傾向のことを指す。例えばランダムアクセス中心なら配列の強みが出やすい。先入れ後出しが自然な処理（関数の入れ子など）ならスタックが適合する。先行要素を先に取り出す必要がある場合はキューが向く。
また、部分的な順序が必要か、完全な順序が必要かでも適切な選択が変わる。順序付き辞書を維持する必要があるなら、探索だけでなく挿入後の整列を支える仕組みが求められる。探索が多いのか更新が多いのかで、同じ構造でも性能の見え方が変わる。
1.3.2 性能と実装容易性のトレードオフ
高性能な構造ほど実装が複雑になりがちで、バグのリスクや保守負担が増えることがある。例えば平衡木や高度なハッシュ衝突対策は、設計とテストの工数が増えやすい。一方で、入力規模が小さい、更新頻度が低い、あるいは平均性能だけを重視できる場合は、シンプルな構造でも十分なことがある。
さらに、実装容易性は単に書きやすさだけでなく、変更時の影響範囲、仕様の明確さ、デバッグのしやすさにも関係する。性能目標と運用条件を揃え、過剰な最適化を避けつつ必要な改善を行う判断が現実的な設計につながる。
2 線形構造
線形構造は、要素が一列に並ぶ関係を基本として扱う。隣接関係（次の要素）だけが中心になるため、実装は比較的理解しやすい一方、先頭や末尾付近以外の挿入・削除にはコストがかかることもある。代表的な例が配列、連結リスト、スタック、キュー、デックである。
2.1 配列
配列は、要素を連続した領域に並べて保持する方式として理解できる。添字から直ちに位置を求められるため、参照が速い性質を持つ。
2.1.1 連続メモリと添字アクセス
配列はメモリ上で連続に確保されることが多く、添字計算により要素の位置を一意に決められる。これにより、要素取得は入力サイズに依存しない一定時間で行えることが一般的である。加えて、連続配置は参照の局所性を高め、走査では効率がよくなりやすい。
2.1.1.1 動的配列（拡張）の考え方
動的配列は、内部の確保容量を上回る挿入が起きた場合に、より大きな領域へ全体を移すことで容量を拡張する。拡張時は移動コストがかかるが、拡張を頻繁に起こさない設計により、平均的には挿入が小さな償却コストで済むと説明されることが多い。実務では、容量の増加率や移動回数の設計が性能へ影響する。
2.1.2 挿入・削除のコスト
配列で先頭側や途中への挿入・削除を行う場合、後続要素のシフトが必要になることがある。結果として操作時間は要素数に比例して増える場合がある。末尾への追加や末尾からの削除のように、シフトが不要なケースでは効率が維持されやすい。つまり、挿入位置の分布が設計上の重要な要素になる。
2.2 連結リスト
連結リストは、各要素が次（または前も）を指す参照を持つことで連なりを表す。挿入・削除は局所的な参照変更で済む場合があり、更新に強い性質を持つ。
2.2.1 単方向・双方向・循環
単方向連結リストは各要素が次を指す。双方向連結リストは前後双方を参照し、逆方向の走査も可能になる。循環連結リストは末尾や先頭の概念が境界としては弱くなり、終端の参照が別の要素を結び続ける形になる。用途によっては、終端処理の簡略化や特定の反復処理の記述をしやすくする。
2.2.2 ポインタ操作と局所性
連結リストは要素がメモリの離れた場所に配置されることが多く、連続走査ではキャッシュ効率が低下しやすい。加えて、参照の辿り方が決まるため、特定要素への到達には先に順番に進む必要がある。とはいえ、挿入や削除はポインタのつなぎ替えで済むことが多く、参照位置が既知であれば操作は軽くなる。
2.3 スタック
スタックは後入れ先出し（LIFO）の規則で要素を管理する抽象構造である。主な操作は積む（push）と取り出す（pop）で、取り出しは常に直近に積まれた要素に限られる。
2.3.1 LIFOの性質
LIFOの性質は、「最後に入ったものが最初に出る」点にある。これにより、処理の入れ子関係に自然に対応できる。例えば再帰呼び出しでは、呼び出しの終了順が逆になるため、スタックによる管理が適する。さらに、取り消し操作（undo）にも関連する考え方がある。
2.3.2 実装と用途（関数呼び出し等）
スタックは配列で実装することも、連結リストで実装することもできる。配列実装では末尾ポインタを進めるだけでよく、実装が簡潔になりやすい。連結リストでは先頭への連結・解除で済む場合がある。用途としては関数呼び出しの戻り先管理、式の評価、括弧の整合性確認などが挙げられる。
2.4 キュー
キューは先入れ先出し（FIFO）の規則で要素を管理する。主要操作は追加（enqueue）と取り出し（dequeue）で、取り出しは最も古い要素から行われる。
2.4.1 FIFOの性質
FIFOは「最初に入ったものが最初に出る」仕組みである。待ち行列としての性質を持つため、順番を保って処理する必要があるタスクに適用できる。例えばプリンタのジョブ管理、イベント処理、プロセッサのスケジューリングなど、到着順の扱いが重要な場面で利用される。
2.4.2 実装（循環キュー等）と用途
キューの実装としては、先頭と末尾を持つ方式がある。配列で単純に実装すると先頭削除のたびにシフトが必要になるが、循環キューを用いると添字を折り返して領域を再利用できる。これにより削除・追加が効率よく行える。さらに、幅優先探索での管理にもキューが利用され、探索の層構造を自然に表現できる。
2.5 デック
デック（deque）は両端キューであり、先頭と末尾の双方から挿入・削除を行える構造である。操作範囲が広いため、状況によっては複数の専用構造を統合して扱える。
2.5.1 両端操作の設計
デックでは、左右どちらからも要素を追加・削除できるように設計する。実装としては循環配列を用いて両端の位置管理を工夫することが多い。加えて、必要に応じて現在のサイズや上限を管理し、端をまたぐ操作でも一貫性を保つ。
2.5.2 代表的な利用場面
デックは「両端から取り出す」必要があるアルゴリズムで出番がある。例えばスライディングウィンドウの最大値を計算する際、候補をデックに保持し、条件を満たさない要素を両端から除外する手順が知られている。状況によっては、順序要件を満たしつつ計算量を抑える設計に寄与する。
3 木構造
木構造は、階層関係を持つデータの整理に向く。根から枝をたどる形で関係が表され、上位から下位への依存を持つことが多い。探索や整理、階層表示などに広く利用される。
3.1 基本概念
木の理解には、構成要素の用語が欠かせない。根、親、子、葉といった関係を押さえることで、探索や走査の仕組みが具体化する。
3.1.1 根・親・子・葉
根は木の最上位に位置する要素である。親はある節点に対して上位側の節点を指し、子は親から直接つながる下位側の節点を意味する。葉は子を持たない節点として定義されることが多い。この分類により、どの節点が終端か、どこから展開できるかを判断できる。
3.1.2 高さと深さ
深さは根からの距離として扱われることが多い。高さは、その節点から最も深い下位までの距離で定義される場合がある。これらは探索コストと関係し、木が深く偏ると操作の時間が増えやすい。したがって高さやバランスの概念は、性能評価の土台になる。
3.2 二分木
二分木は各節点が最大で2つの子を持つ構造である。探索や走査の基本形として位置づけられ、より高度な木構造の基礎にもなる。
3.2.1 探索・挿入の基本
二分木の探索は、節点の値比較や条件に応じて左右どちらへ進むかを決める。ただし一般の二分木では、左右に何が入るかの制約がないため、探索の効率は構造に依存する。挿入も同様に、単に「末端に追加」するか、特定のルールで空き位置を探すかなど、設計によって振る舞いが変わる。
3.2.2 走査（前順・中順・後順）
走査は木の各節点を訪問する順序を定める手続きである。前順は根を先に訪れ、その後に左右部分木を辿る。中順は根と左右部分木の訪問順が入れ替わり、後順は根を最後に訪れる。これらは再帰的定義で表されることが多く、処理の目的（コピー、表現、式の解釈など）に応じて使い分けられる。
3.3 二分探索木
二分探索木（BST）は、節点の値に関する順序条件を満たす二分木である。これにより探索が効率化される。
3.3.1 ルールと探索効率
BSTの基本ルールは、各節点について左部分木の値が節点より小さく、右部分木の値が大きい（または等価の扱いを定める）といった条件を持つことである。この性質により、探索は比較結果に従って片側を捨てられる。結果として高さに比例した時間で探索が進むことになり、平衡度が高いほど高速になる。
3.3.2 バランス崩れの問題
挿入順によっては木が片側に偏り、高さが要素数に近づくことがある。例えば値が単調増加の順で挿入されると、BSTは実質的に連結リストに近い形になり探索が遅くなる。この問題を避けるため、次節の平衡木のように高さを抑える工夫が導入される。
3.4 平衡木
平衡木は、操作の効率が悪化しないように木の高さを制御する設計を持つ。挿入や削除のたびに調整が必要になり得るが、それによって探索の上限を改善できる。
3.4.1 AVL木の考え方
AVL木は、各節点で左右部分木の高さ差が一定の範囲に収まるように保つ。高さ差が大きくなった場合には回転と呼ばれる局所的な構造変更を行い、木の形を整える。これにより探索時間の上限を抑えやすいが、更新時の調整コストが発生する。
3.4.2 赤黒木の考え方
赤黒木は、色（赤・黒）による制約を用いて高さを抑える平衡木である。厳密な高さ差条件だけでなく、色の配置が満たすべき性質に基づいて探索の上限が保証される。AVL木に比べて更新時の調整回数が少なくなりやすいとされ、汎用ライブラリでの採用例も多い。
3.5 ヒープ
ヒープは「親が子に対してある優先関係を満たす」構造で、代表的には最大ヒープや最小ヒープとして説明される。順序全体をソートする必要はなく、最大（または最小）を取り出す操作を効率化する目的が中心になる。
3.5.1 優先度付き待ち行列との関係
ヒープは優先度付き待ち行列（プライオリティキュー）の実装手段として利用される。挿入した要素の中から最優先の要素を素早く取り出す設計に適しており、イベント駆動のシミュレーションや最短経路計算などで頻繁に用いられる。取り出し対象は常にヒープ条件を満たす上端から選ばれる。
3.5.2 ヒープの構築と更新
ヒープの更新では、要素の挿入や削除に伴って条件が崩れるため、その後の調整（上方への伝播、下方への伝播、あるいは両方の手順）が必要になる。構築では、初期配列からヒープ条件を満たすように効率良く調整する方法がある。これらの手順は要素数に対して現実的な計算量を与えるよう設計されている。
3.6 まとめ木（トライ）
トライ（Trie）は、文字列の集合を扱うための木構造である。各節点が文字（または遷移）に対応し、根からの経路が単語や接頭辞を表す。
3.6.1 文字列辞書としての特性
トライは、共通接頭辞を共有できるため、文字列辞書の圧縮に近い利点がある。検索は文字列の各文字に応じた遷移を辿ることで進み、語彙全体の大きさよりも入力文字数に依存しやすい。さらに、辞書に追加された語の重複接頭辞を活かせる点が特徴として挙げられる。
3.6.2 プレフィックス探索
プレフィックス探索では、与えられた接頭辞に一致する語を効率よく列挙できる。トライでは接頭辞に対応する節点まで到達した後、その下位にある語を探索することで候補集合を得られる。これにより「部分一致」や「候補提示」のような検索要件に適合しやすい。
4 グラフ構造とハッシュ構造
グラフは節点と辺（関係）で表され、ネットワーク、路線、依存関係など複雑な関係を扱う。あわせて、ハッシュ表はキーの対応付けを効率化する構造であり、探索を高速化する目的で利用される。
4.1 グラフの表現
グラフの表現方法は性能や操作の実装に直結する。節点数や辺数、よく行う操作（走査、重み計算、近傍列挙）に応じて適した形式が変わる。
4.1.1 隣接行列
隣接行列は、節点数に対して2次元の表を用意し、行と列の対応で辺の有無（や重み）を保持する方式である。辺の判定が高速になりやすい一方、節点が多い場合は行列が巨大になりやすい。疎なグラフでは無駄な領域が増えることがある。
4.1.2 隣接リスト
隣接リストは、各節点に対して接続先の集合（近傍）を列挙する方式である。辺数に比例する形で表現できるため、疎なグラフに適していることが多い。近傍列挙では効率的であるが、特定の辺の有無を即座に確かめるには追加の探索が必要になりやすい。
4.1.3 近接度（エッジ重み・有向無向）
グラフの性質として、辺が重みを持つか、向きを持つかがある。重みがある場合は距離やコストなどを表し、最短経路計算などの応用に直結する。有向グラフでは「行ける方向」が限定され、逆方向の可用性は別に扱う必要がある。無向では関係が双方向として解釈される。
4.2 グラフ探索
グラフ探索は、ある開始点から到達可能な範囲を辿る基本操作である。代表的な手法が幅優先探索と深さ優先探索であり、探索順と到達の性質が異なる。
4.2.1 幅優先探索（BFS）
幅優先探索は、近い節点から順に辿る方針で進む。距離（辺数）で層を作るように探索が進むため、無重み環境では最短経路の考え方と相性がよい。実装上はキューを用いて管理することが多い。
4.2.2 深さ優先探索（DFS）
深さ優先探索は、可能な限り深い経路を辿ってから戻る方針で進む。再帰または明示的なスタックで実装されることが多い。到達の順序はBFSと異なり、連結性の確認、サイクル検出、トポロジカルな処理などへ応用される。
4.3 最短経路と関連構造（概念整理）
最短経路問題は、重み付きグラフにおいて「最小コストでの移動」を求める考え方である。ここでは手法の位置づけを整理し、どの条件で使われやすいかを把握する。
4.3.1 ダイクストラ法の位置づけ
ダイクストラ法は、非負重みの状況で最短距離を効率よく計算する手法として知られる。優先度付き待ち行列を用い、現在確定できる最も有望な距離を次に確定させる方針で進む。負の重みがある場合には条件が崩れるため、適用範囲の理解が重要になる。
4.3.2 ベルマンフォードの位置づけ
ベルマンフォードは、辺の緩和を繰り返すことで最短距離を求める考え方である。ダイクストラ法よりも一般的な条件下で扱えることが多く、加えて負の重みを含む場合の挙動を検討できる。反復回数が必要になりやすく計算量面では負担が増えることがある。
4.4 ハッシュ表
ハッシュ表は、キーをハッシュ関数で整数へ変換し、配列上の位置に対応付けることで高速な参照を狙う構造である。平均的な性能は高いが、衝突への対処が設計の鍵になる。
4.4.1 ハッシュ関数とキー分布
ハッシュ関数はキーをほぼ均等にバケットへ散らすことを目標とする。分布が偏ると特定領域にアクセスが集中し、性能が劣化する。入力データの性質やキーの生成方法により、ハッシュ関数の振る舞いが重要になるため、良好な設計が求められる。
4.4.2 衝突解決（連鎖・オープンアドレス）
衝突解決は、同じ位置に複数キーが割り当てられる状況をどう扱うかである。連鎖法ではバケット内に複数要素を連結して保持する。オープンアドレスでは別の候補位置へ移動して格納し、探索時も同じ規則で候補を辿る。どちらも性能の特性が異なり、負荷率や要素削除の扱いが影響しやすい。
4.5 性能のばらつきと対策
ハッシュ表では平均性能と最悪性能の差が現れやすい。さらに、使用状況により衝突頻度や探索長が変化するため、対策としてリサイズや負荷率管理が重要になる。
4.5.1 最悪ケースへの備え
最悪ケースは、衝突が極端に偏ると発生し得る。対策としては、ハッシュ関数の選定、種の導入（外部からの偏りを避ける設計）、あるいは衝突時の扱いを工夫することで、偏りが起きても探索時間が爆発しないようにする方針が取られる。保証をどこまで求めるかは設計対象の要件に依存する。
4.5.2 リサイズと負荷率管理
負荷率は、格納要素数とバケット数の比で表され、値が高いほど衝突が増えやすい。そこで、一定閾値を超えると配列サイズを増やし、再ハッシュして配置し直すリサイズが行われる。これにより平均性能が維持されやすい一方、拡張時には全体の再配置コストが発生するため、償却的な観点で設計されることが多い。