平成21年度 春期 午前 問6

✓ これが正解エ要素を挿入する場合，数個のポインタを書き換えるだけなので，処理時間は短い。

解説

つなぎ替えだけで済む挿入が得意な側です。

配列と連結リストは、得意なことがちょうど裏返しになっています。配列は添字から場所を計算できるので、どの要素にも一足飛びに届きますが、途中に要素を入れたり抜いたりすると、それより後ろを全部ずらす必要があります。連結リストは各要素が次の要素を指すポインタを持つ形なので、途中に入れるときは前の要素の指し先と新しい要素の指し先を書き替えるだけで済み、要素がいくつあっても手間が変わりません。そのかわり、先頭から順にたどらないと目的の要素に届きません。見分けるときの軸は、その記述が処理時間は短いと結んでいる動きが、たどる側の話なのか、つなぎ替える側の話なのかを読むことです。連結リストで短くなるのは、つなぎ替える側だけです。

ほかの選択肢はなぜ違うのか

• ア要素を更新する場合，ポインタを順番にたど…：順番にたどるという遅い側の動きを挙げながら、処理時間は短いと結んでいます。先頭から一つずつ進む以上、目的の要素までの手間は要素の数に応じて増えていきます。
• イ要素を削除する場合，削除した要素から後ろ…：削除したところより後ろの要素をすべて前へ動かすと述べていますが、それは配列で要素を抜いたときの動きです。指し先を書き替える側では、要素そのものは動きません。
• ウ要素を参照する場合，ランダムにアクセスで…：どの要素へも直接届くと述べていますが、それも添字で場所を計算できる側の性質です。指し先をたどる形では、目的の要素まで順に進むほかありません。