データ構造とアルゴリズム

なぜデータ構造とアルゴリズムが重要なのか、これまで見てきたものをベースにして
メモとしてまとめました。
現在、毎日取り組んでいるアルゴリズム問題に活かせる視点を整理します。

データ構造

プログラム（関数やメソッド、あるいはクラスなど）が、必要なデータを仮想メモリ上でどう組織化・管理するかということ

1. データをどう持つか（ = 構造）

データをどう並べるか（配置）という、「仮想メモリ上にデータをどう配置するか？」という問いに直結します。

• 配列：連続領域（アドレスの間隔が等しい）
• 連結リスト：ノードが点在、ポインタでつながる
• ハッシュテーブル：キーに基づく配置
• 木構造：親子関係を持ち、ポインタまたはインデックスで接続

2. それをどう使うか（ = 操作）

どのようにアクセス・変更するか（操作）

• 検索：配列の走査、ツリーの探索、ハッシュでの検索など
  配列の走査（for i in range(n):）→ メモリを順に読む
  木構造の再帰探索 → スタックを使って親→子をたどる
• 追加／削除：リストの挿入、スタックへのpush/pop、ツリーのバランス維持など
  キュー・スタック操作 → 入出順制御とメモリの先頭・末尾の管理

3. 空間と時間のバランス（設計の意識）※アルゴリズムの視点

• 仮想メモリ上の「どれだけのメモリを使うか（空間計算量）」
• 処理が終わるまで「何ステップかかるか（時間計算量）」

4. それを支えるコード（関数・メソッド）

データ構造を使って意味のある操作をするのが関数・メソッドの役割です。

◎構造をどう組むか（メモリ上でどう配置されるか）と、
◎その構造をどう使うか（関数でどう操作するか）

仮想メモリ上でデータを管理するデータ構造の 2つの意味合い

1. プロセス内部のデータ構造

あるプロセスが、自身の仮想メモリ空間上でどのようにデータを扱うか

→ プロセスが使う 変数・配列・リスト・ツリーなどのプログラム上のデータ構造が仮想メモリ空間内にどう配置され、どう動的に確保・解放されるかということ

（例）ヒープ・スタック、ポインタで繋がるノード（リスト、ツリーなど）

OSにとってはただの仮想メモリの一部でも、アプリケーションレベルでは「構造化されたデータの塊」として使われている

2. OSが仮想メモリ自体を管理するためのデータ構造

OSが、プロセスに割り当てた仮想メモリ空間そのものをどう管理しているか
→ 仮想メモリを管理するデータ構造

（例）Linuxでの構造体

データ構造	役割
mm_struct	プロセスの仮想メモリ空間全体を表す
vm_area_struct	各仮想メモリ領域（スタック、ヒープ、コードなど）を表す
ページテーブル	仮想アドレス→物理アドレスへの対応表（CPU + OS が使う）

OSはこれらを使って、以下のようなことを判断している
・どの範囲が読み取り専用か？
・このアドレスはヒープかスタックか？
・ページフォールトが起きたとき、どう対処すべきか？

プロセスが自分の仮想メモリ空間内で、プログラムの目的に応じてどうデータを配置・管理しているか
この場合、仮想メモリはただの論理的な空間で、そこにどう構造化されたデータ（ツリー、配列、マップなど）を構築するかが開発者の関心事になります。

アルゴリズム問題への向き合い方

設計視点でアルゴリズムを解く力を鍛える

1. 問題文を「データ構造の設計」として読む：何を保持し、どういう操作が求められているか

2. 仮想メモリ空間にどう配置されるかをイメージする

• データが連続しているか？分散しているか？
• アクセスが線形か？ランダムか？再帰的か？

3. 関数はその構造をどう動かすかを考える

• 操作が挿入・削除・検索か？
• データの移動や比較がどこで起きているか？
• スタックやキュー、再帰呼び出しのメモリ使用量は？

4. 空間・時間のトレードオフを検討する

関数とは、仮想メモリ空間上に設計したデータ構造にアクセスし、そのデータの配置と変化（操作）をコントロールするコード上の表現