データ構造の可視化
データ構造は値を保存するだけでなく、速い操作と遅い操作を決めます。ハッシュ衝突、木の探索、ヒープの上昇をコードと並べ、取引を見ます。
よく行う操作から選びます。スタックは最後に積んだ端だけを開き、ハッシュ表はキーから位置を計算して平均的に速く探しますが、キーの整列順を保証しません。平衡木は対数の費用を払い、順序を保ちます。
データ構造の見方
操作ごとに三つを調べます。
- 何が速く、何を払うか：スタックの push と pop は O(1) ですが、先頭だけを扱います。ハッシュ表は平均 O(1) でもキー順の巡回を保証しません。
- どう見つけるか：連結リストはポインターをたどり、ハッシュ表は位置を計算し、BST は比較して左右を選びます。ヒープは極値の端を提供し、任意キーの探索には向きません。
- どの順序を保つか：リスト、スタック、キューは列や投入順を、BST はキー順を、ヒープは極値に必要な部分順序を保ちます。本例のハッシュ表はキー順を持ちません。
操作の比較
平均、最悪、償却の違いに注意します。通常のハッシュ表の大量衝突や非平衡 BST の退化は O(n) になり得ます。リストの定数操作は必要なノードや直前ノードが既知で、位置を探す費用を含みません。スタックとキューの O(1) は両端の操作が定数時間の実装を前提とします。キューのレッスンのコードはリストの pop(0) で取り出すため O(n) です。
| 構造 | 探索 | 挿入 | 削除 | 順序 |
|---|---|---|---|---|
| 動的配列 | O(n)、添字 O(1) | 末尾は償却 O(1)、位置 i は O(n) | 位置 i は O(n) | 添字順 |
| スタック | 任意探索なし | push O(1) | pop O(1) | LIFO、上端のみ |
| 単調スタック（次の大きい値） | 全体走査 O(n) | push O(1) | pop O(1) | 待機候補が底から上へ非増加 |
| キュー | 任意探索なし | enqueue O(1) | dequeue O(1) | FIFO、両端 |
| 単方向リスト | O(n) | 直前が既知なら O(1) | 必要な直前が既知なら O(1) | リンク順 |
| 双方向リスト | O(n)、両端から可能 | ノード既知なら O(1) | ノード既知なら O(1) | 双方向のリンク順 |
| 循環リスト | O(n)、任意ノードから可能 | 必要なノード既知なら O(1) | 必要な直前が既知なら O(1) | 末尾から先頭へ戻る |
| ハッシュ表 | 平均 O(1) | 平均 O(1) | 平均 O(1) | キー順なし |
| 二分探索木 | 平均 O(log n) | 平均 O(log n) | 平均 O(log n) | キー順 |
| AVL 木 | 最悪 O(log n) | 最悪 O(log n) | 最悪 O(log n) | 高さを平衡化したキー順 |
| 赤黒木 | 最悪 O(log n) | 最悪 O(log n) | 最悪 O(log n) | 色の不変条件によるキー順 |
| Trie | O(L) | O(L) | O(L) | 接頭辞の経路 |
| ヒープ | 効率的な任意探索なし | O(log n) | 極値の取り出し O(log n) | 部分的な優先順 |
| Union-Find | 根の検索は償却ほぼ O(1)（ランク併合＋経路圧縮） | 合併は償却ほぼ O(1) | 通常の削除なし | 素な集合 |
| グラフ：リスト／行列 | 辺確認 O(deg(u))／O(1) | 辺追加 O(1)／O(1) | 辺削除 O(deg(u))／O(1) | 隣接関係 |
スタックとキューはアクセスを制限し、ハッシュ表はキー順を持たず、木は配列の O(1) 添字アクセスと引き換えに動的な順序操作を得ます。一列だけでなく、仕事の組み合わせで選びます。
推奨する学習順序
動的配列は連続した保存先で O(1) の添字アクセスを得ます。途中の挿入・削除には O(n) の移動が必要で、満杯なら拡張してコピーするため、末尾追加の定数費用は償却です。次にスタックとキューで LIFO と FIFO の制限を学びます。普通のスタックの直後に単調スタックを学ぶと、同じ push/pop だけで未解決候補を値順に保ち、「右側で最初に大きい値」の走査を O(n) にできること、そして各添字が一度入り最大一度出るという償却解析を具体的に確認できます。
単方向リストはポインターの鎖で、既知位置への挿入は O(1)、位置の探索は O(n) です。双方向リストはポインターを一つ増やし、逆向きの走査と既知ノードの O(1) 削除を得ます。循環リストは末尾を先頭へつなぎ、巡回に使います。終了判定は null ではなく、開始点へ戻ったかになります。
次はハッシュ表のチェイン法とオープンアドレス法です。キーから位置を得た後、別キーが同じ場所を求めた場合を扱います。探索木の前には木の基礎で、根、葉、高さ、深さ、三つの走査順を確認します。
二分探索木は比較して左右へ進み、高さが費用を決めます。AVL 木は高さを保存し、挿入後の LL、RR、LR、RL 回転で最悪経路を対数に保ちます。赤黒木は緩い色の条件で同じ最悪上界を保ち、叔父の色により上向きの再着色か一・二回転の修復を選びます。
Trieは一辺一文字で接頭辞を共有し、接頭辞検索を自然に扱います。グラフ表現は同じ辺を隣接行と正方行列へ保存し、辺の照会と疎な走査の費用を比べます。Union-Findは同じ集団かを答え、ランクによる併合と経路圧縮を組み合わせて償却ほぼ定数にします。Kruskal の巡回検出にも使います。
最後はヒープです。全順序を捨て、極値に必要な順序だけを保ちます。先頭を見るのは O(1)、挿入と極値の取り出しは O(log n) で、優先キューとヒープソートの基礎になります。
データ構造の可視化一覧
構造を選び、操作と入力を変えて、コードと状態の変化を確認してください。