配列で実現した双方向リストへの挿入
出典: 令和5年度 秋期 応用情報技術者試験 午前 問5 (IPA)
双方向リストを三つの一次元配列 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 である要素は，それぞれ双方向リストの末尾，先頭を表す。
- 双方向リストへの要素の追加は，一次元配列の末尾に追加
- ア next[6] ＝ 2，prev[6] ＝ 3
- イ next[6] ＝ 3，prev[6] ＝ 4
- ウ next[6] ＝ 5，prev[6] ＝ 3
- エ next[6] ＝ 5，prev[6] ＝ 4
正解と解説を見る
正解: ウ
- ア: next[6] ＝ 2 だと C の次が F になり、E が抜けてしまいます。D の次は E (5) です。
- イ: next[6] ＝ 3 は D 自身を指していて、prev[6] ＝ 4 は B を指しています。D の次に挿入するので合いません。
- ウ: C の次は E (要素番号 5)、前は D (要素番号 3) なので正しい組合せです。
- エ: prev[6] ＝ 4 は B を指します。C の前は D (要素番号 3) です。
ポイント
- 図のリストを Head からたどると、1 (A) → 4 (B) → 3 (D) → 5 (E) → 2 (F) の順です。
- C は配列の末尾 (要素番号 6) に追加し、D (3) と E (5) の間に入れます。
- C の次は E なので next[6] ＝ 5、C の前は D なので prev[6] ＝ 3 です。
(あわせて next[3] ＝ 6、prev[5] ＝ 6 に書き換えます)