令和元年度秋期 ITストラテジスト 午前Ⅰ 問4

ポインタ参照回数を比べる視点

操作ごとの参照回数を比べるときは、処理の目的だけで判断せず、対象を見つけるまでにどの位置を順にたどる必要があるかを整理します。各段階を分け、同じ条件で数えることが重要です。

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

比較では、参照が発生する場面を操作の開始から終了まで時系列に書き出し、位置の確認、リンクの更新、処理後の確認を混同しないようにします。条件が同じかも併せて見直します。

視点

参照回数は、データ構造の名前から直感的に決めず、ひとつの操作を小さな確認単位へ分解して捉えます。どの参照を一回として扱うかを先にそろえ、比較対象の前提を変えずに整理しましょう。

確認ポイント

• 参照が発生する場面を時系列で整理する
• 一回として数える対象を同じ基準にそろえる
• 操作前後の条件や対象位置を確認する

正解

エ

解説

単方向リストでは、先頭から次のデータへ進むことはできますが、末尾のデータからその直前のデータへ戻れません。末尾のデータを削除するには直前のデータを探してポインタを更新する必要があり、多くの要素を順にたどるため、末尾削除の回数が最も多くなります。

理由

先頭にデータを追加する場合は先頭ポインタを新しいデータへ変更し、新しいデータから従来の先頭へつなげればよいので、探索は不要です。先頭のデータを削除する場合も、先頭ポインタを次のデータへ移すだけで処理できます。

比較

末尾にデータを追加する場合は、末尾ポインタを利用して末尾の次に新しいデータをつなげられます。一方、末尾のデータを削除する場合は、末尾ポインタだけでは直前のデータを特定できません。そのため先頭から順にたどって直前のデータを探し、末尾ポインタとそのポインタを更新する必要があります。

選択肢ア

これは不正解だよ。先頭にデータを追加する処理では、新しいデータを先頭ポインタが指すデータの前につなぎ、先頭ポインタを新しいデータへ変更すればよい。既存のリストを末尾までたどる必要がないため、ポインタをたどる回数は多くならない。

選択肢イ

これは不正解だよ。先頭のデータを削除する処理では、先頭ポインタを現在の先頭データが指す次のデータへ変更すればよい。先頭から順に各データを調べる必要はなく、末尾ポインタの更新も通常は必要ないため、探索回数は少ない。

選択肢ウ

これは不正解だよ。末尾にデータを追加する処理では、末尾ポインタによって現在の末尾データを直接参照できる。新しいデータをその後ろにつなぎ、末尾ポインタを更新すればよく、先頭から多くのデータをたどる必要はない。

選択肢エ（正解）

これは正解だよ。末尾のデータを削除するには、末尾ポインタだけでは直前のデータを参照できない。単方向リストは後ろ向きにたどれないため、先頭から順に進んで直前のデータを探し、そのポインタを更新する必要があり、たどる回数が最も多い。

学習のポイント

単方向リストの各操作について、必要なポインタ更新と探索範囲を比較する。