データ構造 (Data Structures)

概要

• データ構造とは (コンピュータ科学における役割)
• 抽象データ型 (ADT)とデータ構造の関係
• データ構造の分類 (線形構造、非線形構造など)
• データ構造の選択基準 (時間計算量、空間計算量、操作の種類)

---

1. 配列 (Array)

• 基本概念
  • 配列とは (定義、特性、インデックス)
  • 配列のメモリ配置 (連続メモリ領域)
  • 配列の次元 (1次元配列、2次元配列、多次元配列)
• 操作と計算量
  • 配列における要素アクセス (O(1))
  • 配列における要素検索 (線形探索 O(n), 二分探索 O(log n) - ソート済みの場合)
  • 配列の末尾への要素追加 (固定長配列と動的配列)
  • 配列の途中への要素挿入 (O(n))
  • 配列からの要素削除 (O(n))
  • 配列の時間計算量と空間計算量の分析 (まとめ)
• 種類と応用
  • 固定長配列 (Static Array)
  • Resizable Array)
    • 動的配列の仕組み (キャパシティとサイズ)
    • 動的配列のリサイズ戦略 (例: 倍加方式)
    • 動的配列の償却実行時間 (Amortized Time Complexity)
  • 多次元配列
    • 2次元配列 (行列) の表現と操作
    • 2次元配列の行優先格納と列優先格納
  • スパース配列 (疎な配列) とその表現方法
• プログラミング言語における配列
  • C++における配列とポインタ
  • Javaにおける配列とArrayListクラス
  • Pythonにおけるlist型 (動的配列)
  • JavaScriptにおけるArrayオブジェクト
• 利点と欠点
  • 配列のメリット (高速アクセス、メモリ効率)
  • 配列のデメリット (サイズ固定、挿入削除コスト)

2. 連結リスト (Linked List)

• 基本概念
  • 連結リストとは (定義、ノード構造、ポインタ)
  • 連結リストのノード構造 (データ部とポインタ部)
• 操作と計算量
  • 連結リストの先頭への要素追加 (O(1))
  • 連結リストの末尾への要素追加 (O(n) or O(1) if tail pointer exists)
  • 連結リストの特定位置への要素挿入 (O(n) for search, O(1) for insertion)
  • 連結リストからの要素削除 (O(n) for search, O(1) for deletion)
  • 連結リストにおける要素検索 (O(n))
  • 連結リストの時間計算量と空間計算量の分析 (まとめ)
• 種類
  • 単方向連結リスト (Singly Linked List)
  • 双方向連結リスト (Doubly Linked List)
    • 双方向連結リストのノード構造 (prevポインタとnextポインタ)
    • 双方向連結リストの操作 (挿入、削除の利点)
  • 循環連結リスト (Circular Linked List)
    • 単方向循環連結リスト
    • 双方向循環連結リスト
  • ヘッダノードとダミーノードを持つ連結リスト
• 応用
  • スタックの連結リスト実装
  • キューの連結リスト実装
  • 隣接リスト (グラフ表現における利用)
  • メモリ管理 (例: フリーリスト)
  • 大規模なデータセットの管理 (配列の代替)
• 利点と欠点
  • 削除)
  • 連結リストのデメリット (シーケンシャルアクセス、余分なポインタ領域)
• 比較
  • 配列と連結リストの比較

3. スタック (Stack)

• 基本概念
  • スタックとは (LIFO - Last In, First Out の原則)
• 操作
  • top, isEmpty, size)
  • スタック操作の時間計算量
• 実装方法
  • スタックの配列実装
    • 固定長配列によるスタック
    • 動的配列によるスタック
    • スタックオーバーフローとアンダーフロー (配列実装時)
  • スタックの連結リスト実装
• 応用例
  • 関数呼び出しスタック (コールスタック)
  • 式の評価 (中置記法から後置記法への変換、後置記法の評価)
  • 構文解析 (パーサにおける利用)
  • 深さ優先探索 (DFS) アルゴリズムにおける利用
  • リドゥ(Redo)機能の実装
  • 括弧の対応チェック
  • バックトラッキングアルゴリズム

4. キュー (Queue)

• 基本概念
  • キューとは (FIFO - First In, First Out の原則)
• 操作
  • front, isEmpty, size)
  • キュー操作の時間計算量
• 実装方法
  • キューの配列実装
    • リングバッファ (循環キュー) を用いた効率的な配列実装
    • キューオーバーフローとアンダーフロー (配列実装時)
  • キューの連結リスト実装
  • 2つのスタックを用いたキューの実装
• 種類と応用
  • 両端キュー (Deque - Double-ended Queue)
    • Dequeの操作 (addFirst, addLast, removeFirst, removeLastなど)
    • Dequeの実装 (配列、連結リスト)
  • 優先度付きキュー (Priority Queue) (詳細はヒープ MOCで)
  • キューの応用例
    • 幅優先探索 (BFS) アルゴリズムにおける利用
    • プリンタスプーリングなどのジョブスケジューリング
    • イベントドリブンプログラミングにおけるイベントキュー
    • 非同期処理のタスク管理
    • バッファリング (例: ネットワーク通信)

5. ハッシュテーブル (Hash Table)

• 基本概念
  • ハッシュテーブルとは (キーと値のペア、連想配列、辞書)
  • ハッシュテーブルの仕組み (ハッシュ関数、バケット配列)
• ハッシュ関数 (Hash Function)
  • ハッシュ関数とは (役割と重要性)
  • 良いハッシュ関数の特性 (決定性、効率性、一様分布性)
  • 代表的なハッシュ関数の手法
    • 除算法 (Division Method)
    • 乗算法 (Multiplication Method)
    • 文字列に対するハッシュ関数 (例: djb2)
  • 完全ハッシュ関数 (Perfect Hashing) (理論的な概念)
• 衝突 (Collision) と解決法
  • ハッシュ衝突とは (異なるキーが同じハッシュ値になる現象)
  • 衝突解決戦略の概要
  • Separate Chaining)
    • チェイン法の実装 (連結リストや動的配列)
    • チェイン法の性能分析
  • オープンアドレス法 (Open Addressing)
    • オープンアドレス法の仕組み (空きスロットを探す)
    • 線形探査法 (Linear Probing) とその問題点 (一次クラスタリング)
    • 二次探査法 (Quadratic Probing) とその問題点 (二次クラスタリング)
    • ダブルハッシュ法 (Double Hashing)
    • オープンアドレス法における削除処理の課題 (遅延削除)
• 操作と計算量
  • ハッシュテーブルの基本操作 (挿入、検索、削除)
  • ハッシュテーブルの平均時間計算量 (O(1))
  • ハッシュテーブルの最悪時間計算量 (O(n)) とその要因
  • 負荷因子 (Load Factor) とその影響
• リハッシュ (Rehashing)
  • リハッシュとは (負荷因子が閾値を超えた際のテーブル再構築)
  • リハッシュのタイミングとコスト
• 応用例
  • ハッシュオブジェクトの実装
  • キャッシュシステム (例: Webキャッシュ、メモ化)
  • データベースのインデックス
  • シンボルテーブル (コンパイラやインタプリタ)
  • 集合 (Set) データ構造の実装
• 利点と欠点
  • 削除)
  • ハッシュテーブルのデメリット (最悪性能、ハッシュ関数の設計、空間オーバーヘッド)
• 高度なトピック
  • 分散ハッシュテーブル (DHT)
  • Cuckoo Hashing
  • Hopscotch Hashing

6. 木構造 (Tree)

• 基本概念
  • 木構造とは (階層構造、非線形データ構造)
  • 木構造の基本用語 (ルート、ノード、エッジ、親子関係、兄弟、葉ノード、内部ノード、高さ、深さ、次数)
  • 木の特性と定理 (例: n個のノードを持つ木はn-1本のエッジを持つ)
• 木の種類
  • 順序木 (Ordered Tree) と無順序木 (Unordered Tree)
  • 汎用木 (General Tree) とその表現方法 (長男兄弟表現など)
• 二分木 (Binary Tree) MOC
  • 二分木とは (各ノードが高々2つの子を持つ木)
  • 二分木の特性
    • Full Binary Tree の一つの定義)
    • 完全二分木 (Complete Binary Tree)
    • Full Binary Tree のもう一つの定義)
    • Skewed Binary Tree)
  • 参照表現)
  • 二分木の走査 (Traversal)
    • 深さ優先探索 (DFS) に基づく走査
      • 前順走査 (Pre-order Traversal: 親-左-右)
      • 中順走査 (In-order Traversal: 左-親-右) (二分探索木で特に重要)
      • 後順走査 (Post-order Traversal: 左-右-親) (式木の評価など)
    • 幅優先探索 (BFS) に基づく走査 (レベル順走査)
    • 再帰的アルゴリズムによる木走査
    • 非再帰的アルゴリズム (スタックやキューを使用) による木走査
  • 二分木の応用例 (式木、ハフマン木など)
• 二分探索木 (Binary Search Tree - BST) MOC
  • 二分探索木とは (左の子孫 ⇐ 親 ⇐ 右の子孫 の制約)
  • 二分探索木の特性と中順走査によるソート済み順序の取得
  • 二分探索木の基本操作
    • 二分探索木における要素検索
    • 二分探索木への要素挿入
    • 二分探索木からの要素削除 (3つのケース: 葉ノード、子を1つ持つノード、子を2つ持つノード)
    • 二分探索木の最小要素と最大要素の検索
    • 二分探索木における先行者 (Predecessor) と後継者 (Successor) の検索
  • 二分探索木の時間計算量 (平均O(log n), 最悪O(n))
  • 平衡二分探索木 (Balanced Binary Search Tree) MOC
    • 平衡二分探索木の必要性 (性能劣化の防止)
    • AVL木 (Adelson-Velsky and Landis Tree)
      • AVL木の定義とバランスファクタ
      • 二重回転: LR, RL回転)
      • AVL木への挿入と削除アルゴリズム
    • 赤黒木 (Red-Black Tree)
      • 赤黒木の定義と5つの特性 (色、ルート、葉、赤ノード、黒高さ)
      • 赤黒木の回転操作と色変更
      • 赤黒木への挿入と削除アルゴリズム
      • 赤黒木とAVL木の比較
    • (オプション) スプレー木 (Splay Tree) (自己調整型二分探索木)
    • (オプション) Treap (Randomized Binary Search Tree)
  • 二分探索木の利用例 (ソート済みデータの効率的な管理、辞書や集合の実装)
• B木 (B-Tree) とその派生 MOC
  • B木とは (多分岐探索木、ディスクベースのデータ構造向け)
  • B木の特性 (次数m、キーと子の数、高さの低さ)
  • B木の検索、挿入、削除操作の概要
  • B木の利用例 (データベースのインデックス、ファイルシステム)
  • B+木 (B+ Tree)
    • B+木とB木の違い (データは葉ノードのみ、葉ノード間のリンクリスト)
    • B+木の特性と利点 (範囲検索の効率化)
    • B+木の検索、挿入、削除操作の概要
    • B+木の利用例 (データベースのインデックスで主流)
  • (オプション) B*木

7. ヒープ (Heap)

• 基本概念
  • ヒープとは (木構造に基づく優先度付きキューの実装)
  • ヒープ条件 (親子の値の大小関係)
    • 最大ヒープ (Max Heap): 親 >= 子)
    • 最小ヒープ (Min Heap): 親 ⇐ 子)
  • ヒープの構造 (通常、完全二分木またはほぼ完全二分木)
• 実装
  • ヒープの配列実装 (親子関係のインデックス計算)
• 操作
  • bubble-up)
  • get-min)
  • bubble-down)
  • ヒープの構築 (build-heap): 複数の要素から一度にヒープを形成する
  • increase-key)
  • ヒープ操作の時間計算量
• 応用
  • 優先度付きキュー (Priority Queue) の効率的な実装
  • ヒープソート (Heap Sort) アルゴリズム
  • グラフアルゴリズムにおける利用 (例: ダイクストラ法、プリム法)
  • イベントスケジューラの実装
  • システムにおけるタスク管理
  • 小さい要素の効率的な発見
• 種類
  • 二項ヒープ (Binomial Heap) (マージ操作が効率的)
  • フィボナッチヒープ (Fibonacci Heap) (償却計算量が非常に小さい)
  • d-ary ヒープ

8. グラフ (Graph)

• 基本概念
  • 辺(Edge)の集合)
  • グラフの重要性と現実世界での応用例
• グラフの種類と用語
  • Digraph)
  • 重み付きグラフ (Weighted Graph) と重みなしグラフ (Unweighted Graph)
  • 単純グラフ (Simple Graph) と多重グラフ (Multigraph)
  • 自己ループ (Self-loop)
  • 頂点の次数 (Degree): 入次数 (In-degree) と出次数 (Out-degree)
  • パス (Path)、単純パス (Simple Path)、閉路 (Cycle)、単純閉路 (Simple Cycle)
  • 連結グラフ (Connected Graph) と非連結グラフ (Disconnected Graph)
  • 強連結成分 (Strongly Connected Components - SCC) (有向グラフ)
  • 弱連結成分 (Weakly Connected Components) (有向グラフ)
  • 部分グラフ (Subgraph)、誘導部分グラフ (Induced Subgraph)
  • 完全グラフ (Complete Graph)
  • 二部グラフ (Bipartite Graph)
  • 木 (Tree) はグラフの一種 (連結で閉路のない無向グラフ)
  • 有向非巡回グラフ (Directed Acyclic Graph - DAG)
• グラフの表現方法
  • 隣接行列 (Adjacency Matrix)
    • 隣接行列のメリット・デメリット、空間計算量
  • 隣接リスト (Adjacency List)
    • 隣接リストのメリット・デメリット、空間計算量
  • (オプション) 隣接集合 (Adjacency Set)
  • (オプション) 辺リスト (Edge List)
  • (オプション) Incidence Matrix
  • 表現方法の選択基準
• グラフの走査 (Traversal) / 探索 (Search)
  • 幅優先探索 (Breadth-First Search - BFS)
    • BFSのアルゴリズム (キューを使用)
    • BFSの特性 (最短経路探索 - 重みなしグラフ)
    • BFSツリー
  • 深さ優先探索 (Depth-First Search - DFS)
    • DFSのアルゴリズム (スタックまたは再帰を使用)
    • DFSの特性 (閉路検出、トポロジカルソートなど)
    • DFSツリーと辺の分類 (木辺、後退辺、前方辺、横断辺)
• グラフアルゴリズム MOC (主要なアルゴリズム群)
  • 最短経路問題 (Shortest Path Problems)
    • 単一始点最短経路問題 (Single-Source Shortest Path - SSSP)
      • ダイクストラ法 (Dijkstra’s Algorithm) (非負の辺重み)
        • ダイクストラ法の優先度付きキューを用いた実装
      • ベルマンフォード法 (Bellman-Ford Algorithm) (負の辺重み対応、負閉路検出)
      • 有向非巡回グラフ (DAG) における単一始点最短経路 (動的計画法)
    • 全点対最短経路問題 (All-Pairs Shortest Path - APSP)
      • フロイド・ワーシャル法 (Floyd-Warshall Algorithm) (動的計画法)
      • ジョンソン法 (Johnson’s Algorithm) (疎なグラフ向け)
  • 最小全域木 (Minimum Spanning Tree - MST) (連結な無向重み付きグラフ)
    • 最小全域木とは (定義と特性)
    • プリム法 (Prim’s Algorithm)
    • クラスカル法 (Kruskal’s Algorithm) (Union-Findデータ構造の利用)
  • フローネットワーク (Flow Networks) (高度なトピック)
    • 最大フロー問題 (Maximum Flow Problem)
      • フォード・ファルカーソン法 (Ford-Fulkerson Algorithm)
      • エドモンズ・カープアルゴリズム (Edmonds-Karp Algorithm)
    • 最小カット問題 (Minimum Cut Problem)
    • 最大フロー最小カット定理
  • 連結性 (Connectivity)
    • 連結成分の検出 (無向グラフ)
    • 強連結成分の検出 (有向グラフ) (例: Tarjanのアルゴリズム, Kosarajuのアルゴリズム)
    • Cut Edges) の検出
  • 閉路検出 (Cycle Detection)
    • Union-Find)
    • 有向グラフにおける閉路検出 (DFS)
  • トポロジカルソート (Topological Sort) (DAGのみ)
    • トポロジカルソートのアルゴリズム (DFSベース, Kahnのアルゴリズム - 入次数ベース)
    • トポロジカルソートの応用 (タスクスケジューリング、依存関係解決)
  • グラフ彩色 (Graph Coloring) (NP困難問題)
  • マッチング (Matching) (例: 二部グラフの最大マッチング)
• グラフの応用例
  • ソーシャルネットワーク分析
  • 経路探索 (例: GPSナビゲーション)
  • Webページのリンク構造分析 (例: PageRank)
  • 依存関係のモデリング (例: コンパイラの依存関係、プロジェクト管理)
  • 回路設計
  • 推薦システム
  • 生物学におけるネットワーク (例: タンパク質相互作用ネットワーク)

9. (オプション) その他の重要なデータ構造

• Prefix Tree) MOC
  • トライ木とは (文字列検索と接頭辞検索に特化した木構造)
  • トライ木のノード構造とエッジ
  • トライ木の基本的な操作 (挿入、検索、削除)
  • Patricia Trie)
  • トライ木の利用例 (辞書の実装、オートコンプリート機能、スペルチェッカー、IPルーティングテーブル)
• ブルームフィルタ (Bloom Filter) MOC
  • ブルームフィルタとは (確率的データ構造、要素の存在を近似的に判定)
  • ブルームフィルタの仕組み (ビット配列と複数のハッシュ関数)
  • ブルームフィルタの操作 (要素の追加、要素の存在確認)
  • 偽陽性 (False Positive) の確率とその計算 (偽陰性は発生しない)
  • ブルームフィルタの利用例 (大規模データセットにおける要素存在チェック、キャッシュの効率化、ネットワークルータ)
  • (オプション) Counting Bloom Filter
• Union-Find (Disjoint Set Union - DSU) MOC
  • Union-Findデータ構造とは (互いに素な集合の管理)
  • Union-Findの基本操作 (makeSet, find, union)
  • Union-Findの実装 (木構造表現)
  • Union-Findの最適化手法
    • 経路圧縮 (Path Compression)
    • サイズによる合併 (Union by Size)
  • Union-Findの償却計算量
  • Union-Findの利用例 (クラスカル法、連結成分の検出、画像処理)
• セグメント木 (Segment Tree) MOC
  • セグメント木とは (区間に対するクエリ処理に特化した木構造)
  • セグメント木の構築方法
  • 最大値など)
  • セグメント木の更新操作 (点更新、区間更新)
  • 遅延伝播 (Lazy Propagation) による区間更新の効率化
  • セグメント木の利用例 (計算幾何学、RMQ問題、動的な区間集計)
• Fenwick木 (Binary Indexed Tree - BIT) MOC
  • 区間和を効率的に計算・更新)
  • Fenwick木の仕組みと配列表現
  • Fenwick木の更新操作とクエリ操作
  • Fenwick木とセグメント木の比較
  • Fenwick木の利用例 (動的な頻度集計、RMQ問題への応用)
• KD木 (K-dimensional tree) MOC (多次元空間データ構造)
  • KD木とは (k次元空間における点の検索)
  • KD木の構築方法 (軸に沿った分割)
  • KD木の検索操作 (最近傍探索、範囲探索)
  • KD木の利用例 (計算幾何学、機械学習)
• Interval Tree MOC (区間データ構造)
  • Interval Treeとは (区間の検索)
  • Interval Treeの構築と操作
• Skip List MOC (確率的データ構造)
  • Skip Listとは (ソート済みリストの検索、挿入、削除を効率化)
  • Skip Listの構造と確率的レベル割り当て
  • Skip Listの操作と期待計算量