令和元年度秋期 情報処理安全確保支援士 午前Ⅰ 問4

単方向リストの末尾削除は「ひとつ前探し」が必要だよ

単方向リストは、各ノードが「次はこっちだよ」と一方向にしか案内してくれない列車みたいなものだよ。末尾の要素を削除したいときは、末尾そのものだけでなく、その直前のノードを見つけないとつなぎ替えができない。だから先頭から順番にたどって、末尾のひとつ前まで探す必要があるんだ。

この問題で問われていること

追加や削除のたびに、ポインタを何回たどる必要があるかを比べよう。特に単方向リストでは、末尾削除のように「前のノード」が必要な操作ほど、先頭からの走査が発生する点に注目だよ。

Singly Linked List Operation Cost

to delete the tail in a singly linked list、 you must find the previous node by traversal

add head -> O(1)\ndelete head -> O(1)\nadd tail with tail pointer -> O(1)\ndelete tail -> traverse

確認ポイント

• 末尾ポインタがあっても前ノードは分からない。
• 先頭追加・先頭削除は定数回で済む。
• 最も多いのは末尾削除。

正解

エ

出典

問題文と解答は IPA 公開の過去問題冊子・解答例を基にしています。

選択肢ア

これは不正解だよ。先頭にデータを追加するだけなら、行列のいちばん前に新しい人を入れて「次は元の先頭の人ね」とつなぎ直すだけ。先頭ポインタを付け替えればよいので、長い列を全部たどる必要はないんだ。

選択肢イ

これは不正解だよ。先頭のデータを削除するなら、先頭ポインタを「次のデータ」に動かすだけで済むんだ。行列の先頭の人が抜けたら、2番目の人を新しい先頭にするだけ、というイメージだよ。末尾までたどる必要はないんだ。

選択肢ウ

これは不正解だよ。末尾ポインタがあるので、最後尾の場所はすぐ分かるんだ。受付で「最後尾はこちら」と看板が出ている感じだね。そこに新しいデータをつなげて、末尾ポインタを新しいデータへ動かせばよいので、先頭から全部探す必要はないよ。

選択肢エ（正解）

これは正解だよ。単方向の線形リストは、一方通行の道みたいに「先頭から次へ、次へ」としか進めないんだ。末尾のデータを消すには、その1つ前のデータを見つけて「ここで終わり」と付け替える必要があるけど、末尾から前には戻れない。だから先頭からずっとたどる必要があって、いちばん手間がかかるんだよ。