概要
アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。
実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。
配列
- データを1列に並べたもの
- データへのアクセスは容易だが、追加や削除には時間がかかる
- 配列のデータはメモリの連続した領域に順番に格納される
- 固定長のメモリを確保する
- 宣言時に確保（静的確保）
- 実行時に確保（動的確保）
- 固定長のメモリを確保する
計算時間
配列に格納されているデータ数をnとする。
データへのアクセス
- O(1)
- メモリアドレスが添字を使って計算することができるため、データに直接アクセスすることができる。（ランダムアクセス）
データの追加
- O(n)
- 追加する箇所より後ろのデータをすべて1つずつずらす必要がある。
データの削除
- データの追加と同様
実装
- 構造体Arrayには配列のデータ構造を定義する。
- golangには配列があるが、ここではスライスを使って配列のデータ構造を実装する。
- 配列は固定長なので長さ（length)を用意しておく。
- insert
- 条件分岐
- 配列が満杯のとき（=data数がlengthと同じとき）
- 配列の範囲外のアクセスが発生するとき
- データをずらす
- 配列の末尾から任意のindexまでを対象にループでデータをずらす
- ずらし終わった後に配列にデータを追加し、lengthを更新する
- 条件分岐
- delete
- 考え方としてinsertの逆に近い
- 条件分岐
- 配列の範囲外のアクセスだけ考慮すれば良い
- データをへらすので配列が満杯かどうかは条件外
- データをずらす
- indexで指定したデータをunsetする
- 末尾からではなく、任意のindexから末尾に向かってループでデータをずらす
- ずらし終わったら後はlengthの更新をする
- get
- 配列の範囲外へのアクセスだけ考慮してランダムアクセス（添字でデータを参照）
- ノート
参考
- github - TomorrowWu/golang-algorithms
- sliceでarrayを実装したわかりやすいコードだったので参考させて頂いた。