平成21年度 春期 基本情報技術者試験 午前 問6
テクノロジ／アルゴリズム配列と比較した場合の連結リストの特徴に関する記述として，適切なものはどれか。
出典：平成21年度 春期 基本情報技術者試験 午前 問6
- ア要素を更新する場合，ポインタを順番にたどるだけなので，処理時間は短い。
- イ要素を削除する場合，削除した要素から後ろにあるすべての要素を前に移動するので，処理時間は長い。
- ウ要素を参照する場合，ランダムにアクセスできるので，処理時間は短い。
- エ要素を挿入する場合，数個のポインタを書き換えるだけなので，処理時間は短い。
正解：エ
解説
配列は要素が連続したメモリ領域に格納されるためランダムアクセスが高速ですが，途中への挿入・削除は後続要素の移動が必要で時間がかかります。一方，連結リストはポインタで要素をつなぐ構造なので，挿入・削除はポインタの書換えだけで済み高速ですが，要素の参照は先頭から順にたどる必要があるため時間がかかります。
選択肢ごとの解説
- ア誤り。連結リストで要素を更新するには，まず該当要素までポインタをたどる必要があり，配列の直接アクセスに比べて時間がかかります。
- イ誤り。連結リストの削除は，該当要素の前後のポインタを書き換えるだけでよく，後続要素を移動する必要はありません。これは配列の削除の特徴です。
- ウ誤り。連結リストは要素を参照する際にポインタを順にたどる必要があり，配列のようなランダムアクセスはできません。
- エ正しい。連結リストへの挿入は，前後の要素のポインタを数個書き換えるだけで済むため，配列に比べて処理時間が短くなります。