応用情報技術者 2023年 秋期 午前2 問05

配列実装の双方向リスト【午前2解説】

正解の理由

解法ステップ

1. 現在の状態を把握する
   • D の要素番号は 3、D の現在の next[3]=5（D の次は E）、prev[3]=4（D の前は B）であることを確認する。
   • 新規要素は配列末尾の添字 6 に入る。
2. 新規要素 6 のリンク設定（挿入位置に合わせる）
   • prev[6] = 挿入位置（D）の要素番号 = 3
   • next[6] = D が元々指していた次の要素番号 = next[3] = 5
3. 周囲要素のリンク更新
   • D の next を新規要素 6 に更新： next[3] = 6
   • 元の次要素 E の prev を新規要素 6 に更新： prev[5] = 6
4. Head/Tail の更新は不要（今回は末尾でない位置への挿入のため）

選択肢別の誤答解説

• ア（next[6]=2, prev[6]=3）
  誤りです。next[6]=2 とすると要素 6 の次が要素番号 2（elem[2]=F）を指すことになり、D の直後に来る要素としては誤りです。もともと D の次は E（要素番号 5）であり、挿入後に 6 の次が 5 でなければなりません。従って next[6] が 2 である選択肢は不正です。
• イ（next[6]=3, prev[6]=4）
  誤りです。next[6]=3 では 6 の次が D 自身を指すことになり、循環や自己参照を生じます。挿入は D の「直後」に行うため、prev[6] は 3（D）であるべきで、prev[6]=4（B を指す）は不適切です。
• ウ（next[6]=5, prev[6]=3）
  正しいです。上で述べた通り、挿入要素の前は D（3）、挿入要素の次は元の D の次である E（5）になるため、next[6]=5、prev[6]=3 が正しい組合せです。
• エ（next[6]=5, prev[6]=4）
  誤りです。next[6]=5 は正しい方向（6 の次が E）ですが、prev[6]=4 とすると 6 の前が B（4）になってしまい、挿入位置が D（3）の直後という条件に反します。したがって不正です。

よくある誤解

• 「挿入後の next/prev は片方だけ更新すればよい」
  → 片方だけ更新するとリストの整合性が崩れ、要素が辿れなくなります。挿入時は挿入要素自身と周囲（挿入前の前要素と次要素）の両方を更新する必要があります。
• 「配列の末尾に追加＝Tail の次にしか入らない」
  → 問題の「一次元配列の末尾に追加」は物理的な配列位置（添字）に関する説明であり、論理的なリスト上での挿入位置（ここでは D の直後）とは別です。配列の物理末尾（添字 6）に置いても、リンクの設定次第でリスト中の任意の位置に挿入できます。

補足コラム

1. next[X] = next[P]（X の次を P の元の次に設定）
2. prev[X] = P（X の前を P に設定）
3. next[P] = X（P の次を X に更新）
4. もし N が存在すれば prev[N] = X（N の前を X に更新）
   この順序だと途中で参照を失うリスクが低くなります。配列実装では添字 0 を「外部（NULL 相当）」として使う慣例が多い点も覚えておきましょう。

elem = [None, 'A','F','D','B','E', None]
next = [None, 4,0,5,3,2, None]
prev = [None, 0,5,4,1,3, None]
# 挿入位置: P = 3 (D), 新規添字 X = 6 (C)
elem[6] = 'C'
next[6] = next[3]  # 5
prev[6] = 3
next[3] = 6
prev[5] = 6

FAQ