単方向リストで最もポインタをたどる処理
出典: 令和元年度 秋期 応用情報技術者試験 午前 問6 (IPA)
先頭ポインタと末尾ポインタをもち，多くのデータがポインタでつながった単方向の線形リストの処理のうち，先頭ポインタ，末尾ポインタ又は各データのポインタをたどる回数が最も多いものはどれか。ここで，単方向のリストは先頭ポインタからつながっているものとし，追加するデータはポインタをたどらなくても参照できるものとする。
- ア 先頭にデータを追加する処理
- イ 先頭のデータを削除する処理
- ウ 末尾にデータを追加する処理
- エ 末尾のデータを削除する処理
正解と解説を見る
正解: エ
- ア: 先頭に追加するときは、先頭ポインタを書き換えるだけで、たどる回数はわずかです。
- イ: 先頭を削除するときは、先頭ポインタを 2 番目のデータに付け替えるだけで、たどる回数はわずかです。
- ウ: 末尾に追加するときは、末尾ポインタから末尾のデータがすぐ分かるので、たどる回数はわずかです。
- エ: 末尾を削除するには、末尾の 1 つ手前のデータを先頭から順にたどって探す必要があるので、たどる回数が最も多くなります。正しい答えです。
ポイント
- 単方向リストは、先頭から次のデータへの向きにしかたどれません。
- 末尾のデータを削除するには、末尾の 1 つ手前のデータ のポインタを書き換え (次は無し)、末尾ポインタもそのデータに付け替える必要があります。
- 手前のデータを見つけるには、先頭から順にたどるしかない ので、たどる回数が最も多くなります。