データ構造 (全53問中38問目)
No.38
配列と比較した場合の連結リストの特徴に関する記述として，適切なものはどれか。
出典：平成21年春期 問6
- 要素を更新する場合，ポインタを順番にたどるだけなので，処理時間は短い。
- 要素を削除する場合，削除した要素から後ろにあるすべての要素を前に移動するので，処理時間は長い。
- 要素を参照する場合，ランダムにアクセスできるので，処理時間は短い。
- 要素を挿入する場合，数個のポインタを書き換えるだけなので，処理時間は短い。
分類
テクノロジ系 » アルゴリズムとプログラミング » データ構造
正解
エ
解説
連結リストは、値の後ろに次の要素のデータ位置を示すポインタを付けデータを連結していくデータ構造です。
配列との比較ですが、配列ではポインタをたどっていく必要がないためデータの更新や参照は高速です。しかし配列への要素の挿入・削除の際には、位置が変化することになる対象要素すべてを移動しなければなりませんので、数個の要素のポインタを付け替えるだけでできる連結リストのほうが高速に処理できます。
- 更新対象の要素までポインタをたどっていく分、リスト構造の更新処理は配列より遅くなります。
- 要素の削除時はポインタの付け替えで順番を変更できるリスト構造のほうが高速です。
- 連結リストはデータにランダムにアクセスできず、目的のデータを参照するためには先頭（双方向リストでは末尾も可）から順番にポインタをたどっていく必要があります。
- 正しい。要素の挿入をする際は、挿入する要素のポインタを正しくセットして、前の要素のポインタを挿入する要素に向けるだけなので、全体を移動しなければならない配列と比較して高速です。