ゼロフィルのリンクトリスト
配列が与えられる。前から順に走査したい。削除をしたい。
要件
元の配列が長さNでも、削除後が長さMならO(M)で走査できる必要がある
ダミーの値を代入して読み飛ばす方式はNG
削除はO(1)でなければならない
要素を詰めるのはNG
PythonのリストのremoveはNG
与えられた配列と同じサイズのゼロフィルされた配列next, prevを用意する
https://gyazo.com/b47c0b5b99311be04ae196ae96bd02bd
削除する時
https://gyazo.com/585a271028f339d5297727f2368c2dbf
code:python
prev[pos + 1 + nextpos] += prevpos + 1 next[pos - 1 - prevpos] += nextpos + 1 単純に構築するとnext[pos] = pos + 1が初期値になるわけだが、そこからの差分だけを持つことでゼロフィルで初期化できるようにしたわけだ。
削除しかしないなら絶対アドレスを持つ必要がないからこれでよい。挿入もするなら普通の双方向リストが良い。
先頭要素は番兵。削除してはいけない。
削除するとどうなるかはまだ考察してない。
作成時のインデックスでのランダムアクセスはO(1)