データ構造とアルゴリズム
配列と比べたときの連結リスト(各要素が次の要素の位置を指すポインタを持つリスト)の特徴として正しいものはどれか。
- A挿入する位置の直前の要素が分かっていれば、ほかの要素を動かさずにポインタの付け替えだけで挿入できるが、i 番目の要素を読むには先頭から順にたどる必要がある
- Bi 番目の要素の位置を計算で求められるので、どの要素も一定の時間 O(1) で読み出せる
- C要素がメモリ上に隙間なく連続して並ぶので、順に読むときにキャッシュやプリフェッチが効きやすい
答えと解説を見る
正解：A. 挿入する位置の直前の要素が分かっていれば、ほかの要素を動かさずにポインタの付け替えだけで挿入できるが、i 番目の要素を読むには先頭から順にたどる必要がある
連結リストでは、挿入や削除の位置が分かっていれば、前後のポインタを書き換えるだけで O(1) で済みます。一方、i 番目の要素を読むには先頭から i 回ポインタをたどる必要があり、O(n) かかります。配列は先頭の番地と要素の大きさから i 番目の番地を計算できるので O(1) で読めますが、途中への挿入には後ろの要素をずらす O(n) の手間がかかります。また、配列は要素が連続して並ぶためキャッシュやプリフェッチが効きやすく、メモリ上に散らばりやすい連結リストは、同じ O(n) の走査でも大幅に遅くなることがあります。
- A. 正しい。挿入・削除はポインタの付け替えで済みますが、位置を指定した読み出しは先頭からたどります。
- B. 番地を計算で求めて O(1) で読めるのは配列の特徴です。
- C. 要素が連続して並びキャッシュが効きやすいのは配列です。連結リストの要素は散らばりやすくなります。