令和元年度 秋期 午前 問6

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

解説

末尾を消すには、その一つ前を先頭から探しに行きます。

単方向の線形リストは、それぞれの要素が次の要素だけを指しています。先頭ポインタと末尾ポインタがあるため、両端そのものには一手で届きます。末尾を削除するときは、削除した後に末尾となる要素、つまり一つ手前の要素を新しい末尾として指し直さなければなりません。ところが手前へ戻るつながりを持っていないので、先頭から順に進んで最後の一つ前まで行き着くほかに方法がありません。要素が多いほどたどる回数は増え、比べた四つの中で最も多くなります。残る三つは、いずれも端のポインタとその先を見るだけで済みます。要素数によらず手数が変わらない処理と、要素数に比例して増える処理という分かれ方になっている点が要点です。双方向のつながりにしておけば、この削除も一手で終わり、手数は要素数に左右されなくなります。

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

• ア先頭にデータを追加する処理：先頭に追加する処理は、新しい要素の次を今の先頭へ向け、先頭ポインタを付け替えるだけで完了します。たどるのは先頭ポインタの一手にとどまり、要素がいくら増えても回数そのものは変わりません。端をつかんでいる強みが出ます。
• イ先頭のデータを削除する処理：先頭を削除する処理は、先頭ポインタから一つ先を読み、それを新しい先頭として指し直すだけです。見るのは二つの要素にとどまり、後ろへ進んで探す必要がありません。こちらも要素数に左右されない処理です。端から一つ進むだけです。
• ウ末尾にデータを追加する処理：末尾に追加する処理は、末尾ポインタが指す要素の次を新しい要素へ向け、末尾ポインタを付け替えます。加える要素はたどらなくても参照できると設問に断ってあるため、ここでも少ない手数で終わります。末尾を直接つかめる強みです。