3つの配列で実現した双方向リストへの要素の挿入とポインタの値

初期状態の各配列の内容を確認します。 Head = 1，Tail = 2 要素番号1（A）: next[1] = 4, prev[1] = 0 （先頭） 要素番号4（B）: next[4] = 3, prev[4] = 1 要素番号3（D）: next[3] = 5, prev[3] = 4 要素番号5（E）: next[5] = 2, prev[5] = 3 要素番号2（F）: next[2] = 0, prev[2] = 5 （末尾） 現在の双方向リストの順序は「A(1) → B(4) → D(3) → E(5) → F(2)」です。 「要素 D（要素番号 3）の次に要素 C を挿入」します。新要素 C は配列の末尾（要素番号 6）に追加されます。 挿入後のリスト順序は「A(1) → B(4) → D(3) → C(6) → E(5) → F(2)」となります。 したがって，要素番号 6（C）のポインタは次のようになります。 next[6]: 次の要素は E（要素番号 5）なので 5 prev[6]: 前の要素は D（要素番号 3）なので 3 よって next[6] = 5, prev[6] = 3 となり，正解はウです。 要素番号 1 4 3 6（追加） 5 2 elem A B D C E F next 4 3 5→6 5 2 0 prev 0 1 4 3 3→6 5 リストの順（A→B→D→E→F）に並べ替えた表です。D と E の間に C（要素番号6）を入れるので、C の next は E の要素番号5、prev は D の要素番号3 になります。D の next と E の prev も6に書き換えます。

双方向リストを三つの一次元配列 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 である要素は，それぞれ双方向リストの末尾，先頭を表す。

  • 双方向リストへの要素の追加は，一次元配列の末尾に追加

問5 双方向リストの配列状態図
出典令和5年度 秋期 応用情報技術者試験 午前 問5

next[6]

prev[6]

ア

2

3

イ

3

4

ウ

5

3

エ

5

4