基本情報技術者 2012年 春期 午前（科目A） 問07

単方向リストのポインタ参照回数【午前解説】

正解の理由

解法ステップ

1. 問題文から「単方向リスト」「先頭ポインタ」「末尾ポインタあり」を確認する。
2. 各操作についてどのポインタ（head, tail, node.next）を参照・更新するかを列挙する。
3. 参照が定数回で済む操作と、リストを順に辿る必要がある操作（$O(n)$）を分ける。
4. $O(n)$ となる操作が最も多く参照するため、それを正解とする。

選択肢別の誤答解説

• ア: リストの先頭にデータを挿入する。
  • 手順：新ノード.next = head; head = 新ノード; 空リスト時は tail = 新ノード。
  • 参照回数は定数（head の読み出しと数回の更新）で済むため最も多くはない。
• イ: リストの先頭のデータを削除する。
  • 手順：head = head.next; 空になれば tail = null。
  • こちらも参照は定数回で完了する（head の参照と更新のみ）。
• ウ: リストの末尾にデータを挿入する。
  • 手順：tail.next = 新ノード; tail = 新ノード; 空リスト時は head = 新ノード。
  • 末尾ポインタがあるため定数回の参照で済む（tail を直接使える）。
• エ: リストの末尾のデータを削除する。
  • 手順：前駆ノードを見つけるために先頭から node.next を繰り返し参照し、見つかったら前駆.next = null; tail = 前駆。
  • 最悪で $n-1$ 回の next 参照が必要になるので最も多い参照回数になる。

よくある誤解

• 「末尾ポインタがあるから末尾削除も高速」は誤り。末尾ポインタは最後のノード自体を示すだけで、その前のノードは分からないため探索が必要です。
• 「ポインタの更新＝参照回数」と混同してしまう点。読む（参照）回数と書き換える（代入）回数は別であり、問題は参照回数を問う点に注意します。
• 「要素数1ならどれも同じ」は特殊ケースで等しくても、問題は一般的な多数データ（大きな $n$）を想定している点を見落としがちです。

補足コラム

• 単方向リストの末尾削除を O(1) にする方法：各ノードに「前ポインタ」を持たせて双方向リストにする、あるいは末尾の直前ノードも別に保持しておく（追加コストが発生）。どれを選ぶかはメモリと操作頻度のトレードオフです。
• センチネル（ダミーヘッド）や循環リストなどの設計でも指し示す参照の扱いが変わり、実装上の境界処理を簡単にできますが、前駆ノード検索の必要性自体は単方向では変わりません。
• 実装上は「参照回数」と「代入回数」を区別して考えると問題の設問意図が明確になります。

FAQ