データ構造

チェックポイント

• 配列 Basis 配列は同じ型の要素を連続したメモリブロックに格納し、インデックスによる任意要素へのアクセスを O(1) で実現する。インデックス参照がハードウェアレベルでどう機能するか、Zig で固定長配列と柔軟なスライスをどう使うか、そして配列のストレージをヒープに移す場面を学ぶ。
• データ構造入門 Basis データ構造とは、特定の操作を効率よく行えるよう、意図的にデータを整理する方法だ。このチェックポイントでは、整理することがなぜ重要なのかを説明し、シリーズ全体で使う用語を紹介し、これから学ぶ構造の概観を示す。
• グラフ Basis グラフは辺で結ばれた頂点の集合であり、ネットワーク・依存関係・関係性をモデル化するための柔軟な構造だ。有向グラフと無向グラフ、重み付き辺、パス、閉路、木や DAG などの主要なグラフの種類を学ぶ。
• 連結リスト Basis 連結リスト（linked list）は要素を連続したメモリに格納するのではなく、ポインタでノードをつなぐ構造だ。既知の位置での挿入・削除が $O(1)$ である代わりに、インデックスアクセスは $O(n)$ になる。
• キュー Basis キュー（queue）は先入れ先出し（FIFO）のデータ構造で、要素は後ろから追加され、前から取り出される。このチェックポイントでは、スタックとの違いを対比しながら、配列およびリスト実装を解説し、BFS やスケジューリングなど FIFO 順序が必要なアルゴリズムを概観する。
• スタック Basis スタック（stack）は後入れ先出し（LIFO）のデータ構造で、関数呼び出しの管理、式の評価、バックトラッキングアルゴリズムなど、プログラムの根幹を支える仕組みだ。