リスト

概要

メモリ上での位置はパラパラとしている

要素の先頭への追加はO(1)

要素の先頭へのアクセスはO(1)

要素の探索にはO(n)

要素の挿入・削除が早いO(1)

→ポインタを繋ぎ直すだけ

ランダムアクセスに時間がかかるので探索アルゴリズムにはほぼ使えない

双方向リスト

要素を先頭、末尾へO(1)で追加できる

順方向、逆方向に辿れる

ポインタの分多くメモリを使用する