- 549 名前：デフォルトの名無しさん mailto:sage [2021/11/29(月) 00:15:16.20 ID:uM27l7Qv.net]
- 前から別の人が指摘しているけど、
リンクドリストとは別に配列を用意してリンクドリストの要素へのアドレスを保持するからリンクドリストの任意の要素にはO(1)でアクセスできる
と主張しているが
そのリンクドリストに追加または削除するたびに配列の要素も追加か削除しないといけなくなる。
リンクドリストの任意の位置に追加/削除するのはO(1)だけど、配列の任意の位置に要素を追加/削除するのはO(1)じゃない。
だからリンクドリストと配列を組み合わせて使うとリンクドリストのメリット(任意の位置への追加/削除がO(1))が無くなってしまう。
その配列に静的配列を使うならリンクドリストの最大サイズを予想してあらかじめ大きな配列を用意しないといけない。
動的配列を使うな要素を追加したときにときどきヒープの再確保がおきる。
