平成22年度 秋期 午前 問5

✓ これが正解エ末尾のデータを削除する処理

解説

単方向リストでは末尾の 1 つ前へ戻る道がありません。

設問は条件を 4 つ与えています。先頭を指すポインタがあること、末尾を指すポインタがあること、各データは次だけを指すこと、そして追加するデータ自体はポインタをたどらなくても参照できることです。この条件のもとで、つないだ先をたどる回数を 4 つの処理ごとに数えます。鍵になるのは、線形リストが次の方向にしか進めないという性質です。ある位置の 1 つ前を知りたくなった瞬間だけ、先頭から歩き直すことになります。末尾を取り除く処理では、取り除いたあとにその 1 つ前を新しい末尾にしなければなりません。ところが後ろから前へ戻る道がないので、先頭から 1 つ前の位置まで順にたどるしかなく、データの個数が増えるほど回数も増えます。これが正解です。ポインタは、その位置に着くのを速くするだけで、その手前が必要になる操作までは速くしません。ここを押さえると、どのポインタが付いていても事情が変わらない処理を見分けられます。

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

• ア先頭にデータを追加する処理：新しいデータの次に元の先頭をつなぎ、先頭ポインタを付け替えれば終わります。歩き直す場面がないので、たどる回数はデータの個数に左右されません。
• イ先頭のデータを削除する処理：先頭の次に当たる位置を読んで、そこを新しい先頭にするだけで済みます。必要な情報が先頭ポインタのすぐ隣にあるため、回数は一定にとどまります。
• ウ末尾にデータを追加する処理：末尾ポインタがある前提なので、端まで歩く必要がありません。今の末尾の次に新しいデータをつなぎ、末尾ポインタを付け替えれば終わるので回数は増えません。