基本情報技術者 2023年 科目A 問02

双方向連結リストの挿入【午前解説】

正解の理由

解法ステップ

1. 元のポインタを把握する
   • A.next = 300（K）、A.prev = 0
   • K.next = 200（T）、K.prev = 100（A）
   • T.next = 0、T.prev = 300（K）
2. 挿入後に新ノードG(400) に設定すべき値を決める
   • G.prev = Aのアドレス = 100
   • G.next = Kのアドレス = 300
3. 既存ノードのポインタを更新する（必要なものだけ）
   • A.nextをGのアドレス（400）に変更 → aが変わる
   • K.prevをGのアドレス（400）に変更 → fが変わる
4. その他（影響のないポインタ）は変更しない
   • A.prev（b）は0のまま、K.next（e）は200のまま、Tのc,dも変わらない

• $G.prev\leftarrow 100,G.next\leftarrow 300$
• $A.next\leftarrow 400,K.prev\leftarrow 400$

選択肢別の誤答解説

• ア: a, b, e, f
  • b（A.prev）は挿入位置が先頭ではないので0のまま変わりません。e（K.next）もKの次はTのままで変化しないため誤りです。
• イ: a, e, f
  • e（K.next）は変化しません。Kの前ポインタだけが更新されるため不正解です。
• ウ: a, f
  • 正しい。AのnextとKのprevのみがGを指すように更新されます。
• エ: b, e
  • b, eともに変化しないポインタなので誤りです。

よくある誤解

• 「挿入すると隣接するノード両方のnextとprevが全部変わる」と考える：挿入では新ノードが挟まる側のポインタだけ（Aのnext、Kのprev）が変わり、A.prevやK.nextは通常変わりません。
• 「新ノードのポインタ値（x, y）を見るだけで答えられる」と思う：新ノードの値は決まりますが、設問は「追加前と比べて値が変わる既存ポインタ」を問うため、既存ノードの変化を検討する必要があります。

補足コラム

• 双方向連結リストの挿入操作は「新ノードのprev/nextを設定」→「隣接ノードの該当ポインタを更新」の順で行うと安全です。順序を誤ると途中で参照が切れてしまうことがあります。
• 先頭や末尾に挿入する場合は、ヘッドやテイル（あるいはNULLを表す値）も更新対象になる点に注意してください。

FAQ