基本情報技術者 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