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

問題文

双方向リストを三つの一次元配列elem[i]、next[i]、prev[i]の組で実現する。双方向リストが図の状態のとき、要素Dの次に要素Cを挿入した後のnext[6]、prev[6]の値の組合せはどれか。ここで、双方向リストは次のように表現する。　　・双方向リストの要素は、elem[i]に値、next[i] に次の要素の要素番号、prev[i]に前の要素の要素番号を設定　・双方向リストの先頭、末尾の要素番号は、それぞれ変数Head, Tailに設定　・next[i]、prev[i]の値が0である要素は、それぞれ双方向リストの末尾、先頭を表す。　・双方向リストへの要素の追加は、一次元配列の末尾に追加

🖊️ 解答を隠して解いてみる

選択肢

ア：

イ：

ウ：（正解）

エ：

🔒 解説は解答すると表示されます

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

正解の理由

図の状態で要素Dは要素番号3にあり、その次に要素C（新規要素、配列末尾の要素番号6）を挿入する操作では、挿入位置の前後のつながりを正しく更新する必要があります。具体的には、挿入する要素6の前はD（要素番号3）なのでprev[6]=3、挿入後に6の次は元のDの次であったE（要素番号5）なのでnext[6]=5になります。以上から、選択肢のウが正しい組合せです。

解法ステップ

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

この手順で最終的にnext[6]=5、prev[6]=3が得られます。

選択肢別の誤答解説

ア（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）に置いても、リンクの設定次第でリスト中の任意の位置に挿入できます。

補足コラム

配列で双方向リストを実装する際、操作の順序に注意すると安全です。挿入の一般的な安全順序は次のとおりです（挿入要素をX、挿入前の要素をP、元の次要素をNとした場合）。

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

例：今回の更新（Pythonによる簡易シミュレーション）

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

Q1. 挿入がリストの末尾（Tailの直後）ならどう変わる？
A1. Tailの直後に挿入する場合、next[new]=0（末尾を表す）に設定し、prev[new]=oldTail、さらにTailをnewに更新します。

Q2. 削除操作は挿入と逆順で更新すればよい？
A2. 基本は逆順で構いません。削除では周囲のリンクをつなぎ直した後、削除要素のnext/prevをクリア（0にするなど）すると安全です。

Q3. 添字があふれたらどうする？
A3. 配列が固定長で満杯の場合は拡張（再確保）か、フリーノード管理（空きリスト）を用いて空き添字を再利用します。

関連キーワード: 双方向リスト、連結リスト、配列実装、挿入操作、next配列、prev配列、添字管理

← 前の問題へこの年度をクイズで解く次の問題へ →

\ せっかくなら /

応用情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！