基本情報技術者 2010年 春期 午前（科目A） 問05
問題文
双方向のポインタをもつリスト構造のデータを表に示す。この表において新たな社員G を社員A と社員K の間に追加する。追加後の表のポインタ a～f の中で追加前と比べて値が変わるポインタだけをすべて列挙したものはどれか。
選択肢
ア：a, b, e, f
イ：a, e, f
ウ：a, f（正解）
エ：b, e
🔒 解説は解答すると表示されます
双方向リストの挿入操作【午前解説】
正解の理由
正解: ウ
元の表からリストは A(100) → K(300) → T(200) の順です。G(400)をAとKの間に挿入すると、新ノードGの前ポインタはAのアドレス100、次ポインタはKのアドレス300になります。これに伴い、Aの次ポインタ（a）が旧値300から新値400へ、Kの前ポインタ（f）が旧値100から新値400へ書き換わります。他の既存ポインタ（Aの前b、Kの次e、Tのポインタc,d）は元の参照先を変えないため不変です。
元の表からリストは A(100) → K(300) → T(200) の順です。G(400)をAとKの間に挿入すると、新ノードGの前ポインタはAのアドレス100、次ポインタはKのアドレス300になります。これに伴い、Aの次ポインタ（a）が旧値300から新値400へ、Kの前ポインタ（f）が旧値100から新値400へ書き換わります。他の既存ポインタ（Aの前b、Kの次e、Tのポインタc,d）は元の参照先を変えないため不変です。
解法ステップ
- 元の表からノードの連結順を把握する（A→K→T）。
- 挿入位置が A と K の間であることを確認する。
- 新ノードGの next を K（300）、prev を A（100）に設定する。
- A の next（a）を新ノードのアドレス（400）に更新する。
- K の prev（f）を新ノードのアドレス（400）に更新する。
- これ以外のポインタ（b, c, d, e）は元の値のまま残るため変更不要と判断する。
（変化するポインタ）→ a, f
（不変のポインタ）→ b=0, c=0, d=300, e=200
（新ノード）→ x(next)=300, y(prev)=100
（不変のポインタ）→ b=0, c=0, d=300, e=200
（新ノード）→ x(next)=300, y(prev)=100
選択肢別の誤答解説
- ア: a, b, e, f
- 誤り：b（Aの前）はもともと0で、挿入位置がAの前ではないため変更不要です。e（Kの次）も200のままで変わりません。
- イ: a, e, f
- 誤り：e（Kの次）は挿入で変わらないため不要な選択肢です。aとfは正しいがeが余分です。
- ウ: a, f
- 正解：Aの次(a)とKの前(f)のみが挿入操作で変更されます。
- エ: b, e
- 誤り：b（Aの前）とe（Kの次）はどちらも元の値のままで、挿入で変更されません。
よくある誤解
- 挿入で周辺の「すべての」ポインタを書き換える必要があると考える誤り。実際は左右の隣接ノードの該当ポインタのみ更新します。
- next と prev を取り違えて、Aの前(b)やKの次(e)を変更すべきと考える誤り。向き（next/prev）の役割を常に確認してください。
- NULL を意味する 0 を新しいノードで上書きすべきだと誤解するケース。head/tail に挿入する場合のみ0の扱いに注意します。
補足コラム
双方向連結リスト（ダブルリンクドリスト）での挿入は局所的な更新で済むのが利点です。一般的な挿入（ノード newNode を p と q の間に入れる場合）の手順と擬似コードは以下の通りです。
-
理論式（p の次が q のとき）:
- new.prev = p.address
- new.next = q.address
- p.next = new.address
- q.prev = new.address
-
Python風擬似実装例:
# nodes: dict[address] = {'next': addr_next, 'prev': addr_prev}
def insert_between(nodes, p_addr, q_addr, new_addr):
nodes[new_addr] = {'next': q_addr, 'prev': p_addr}
nodes[p_addr]['next'] = new_addr
nodes[q_addr]['prev'] = new_addr
ヘッドやテイルに挿入する場合は、p または q が0（NULL）になる点に注意し、外部の先頭ポインタや末尾ポインタの更新が必要です。
FAQ
Q: もしGをリストの先頭に挿入するならどのポインタを変えるか？
A: 先頭挿入なら元の先頭の prev を新ノードで更新し、新ノードの next を元の先頭に、リスト全体のヘッドポインタも新ノードに変更します。
A: 先頭挿入なら元の先頭の prev を新ノードで更新し、新ノードの next を元の先頭に、リスト全体のヘッドポインタも新ノードに変更します。
Q: 問題の0は何を意味するか？
A: 0 は NULL を表し、先頭（prev=0）や末尾（next=0）を示します。NULL は通常のアドレスとは異なり参照先が無いことを意味します。
A: 0 は NULL を表し、先頭（prev=0）や末尾（next=0）を示します。NULL は通常のアドレスとは異なり参照先が無いことを意味します。
Q: 新規ノードのアドレスが既存のアドレスと重複したら？
A: 実務ではアドレス重複は許されないため新しい一意のアドレスを使用します。試験問題では与えられた数字をそのまま使います。
A: 実務ではアドレス重複は許されないため新しい一意のアドレスを使用します。試験問題では与えられた数字をそのまま使います。
関連キーワード: 双方向リスト、ダブルリンクドリスト、ポインタ操作、挿入処理、アドレス、next、prev
\ せっかくなら /
基本情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！