データ構造
データ構造とは、データの順番や位置関係を定めたもの。データをメモリに保存していく際、目的にあったデータ構造にすることで、処理効率を高めることができる。
リスト
- 各データがポインタを持ち、ポインタは次のデータを示す。
- ポインタを頭から辿ることしかできないので、アクセスに時間がかかる。順番にデータを辿ることをシーケンシャルアクセスという。
- 追加や削除は、ポインタを操作するだけなので簡単。
- アクセスするときはO(n)。追加・削除はO(1)。
- 普通のリストは、最後尾のデータはポインタを持っていないが、先頭のデータを指すポインタを持たせることで環状リストになる。
- 普通のリストは、次のデータを指すポインタを1つ持っているが、前のデータを指すポインタも持たせることで双方向リストになる。（ポインタを2つ持つ）
配列
- 添字を使って直接データにアクセスできる。このことをランダムアクセスという。
- アクセスは簡単だが、追加や削除は後述の理由で時間がかかる。
- 追加する時は、まず配列の最後に空間を追加し、追加したい場所まで1つずつデータをずらし、空いた空間にデータを追加する。
- 削除する時は、まずデータを削除し、空いた空間に1つずつデータをずらして埋めていき、空いた空間が最後になったらその空間を削除する。
- アクセスするときはO(1)。追加・削除はO(n)。
スタック
- Last In First Out(LIFO)。後入れ先出しのデータ構造。
- データを追加することをpush, 取り出すことをpopという。
- 常に最新のデータにアクセスしたいときに有効
キュー
ハッシュテーブル
- データをハッシュ化 -> mod演算 -> その結果によって配列のどこに格納するかを決定する
- 適当に配列の最初からデータを挿入していくと、取り出すとき線形探索するしかない
- ハッシュ化〜mod演算をもとに格納場所を決定していれば、取り出すときにハッシュ化〜mod演算することで格納場所を特定できる
- 格納する場所が衝突してしまった場合、データをリスト化する。
ヒープ
- 木構造の1種で、データを自由に追加できるが、取り出せるのは最小値からのみ。最小値を頻繁に取り出す場合に便利。
- 子は親より必ず小さい。ノードは2つまで子を持てる。
- データを追加するときは、一番下の段に左詰め。無理なら新たな段を作る。親と子を比較し、親＞子であれば親と子を入れ替える。入れ替えが発生しなくなるまで繰り返す。
- データを取り出したとき、一番上の数字（一番小さい数字）が取り出される。その後ヒープが再構築される。
- 再構築の手順は、最後尾の数（一番下の段で一番右）を、一番上に移動する。親＞子の場合、より小さい子と入れ替える。入れ替えが発生しなくなるまで繰り返す。
- 取り出すのはO(1)。取り出した後の再構築、データの追加はO(log n)。
2分探索木
- 木構造の一種で、ノードは2つまで子を持てる。
- そのノードのデータは、そのノードの左部分木のどの数よりも大きい。
- そのノードのデータは、そのノードの右部分木のどの数よりも小さい。
- よって2分探索木の最小値は、最上部から見て左部分木の末端。最大値は、右部分木の末端。
