AP 令和5年度秋期問5

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

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

　ウ

　要素Cを挿入する前の状態（要素番号5までの状態）では、Headおよびnextの情報から
　　1(A) → 4(B) → 3(D) → 5(E) → 2(F) → 0
という順序であることがわかります。

　ここで、要素Dの次に要素Cを挿入すると
　　1(A) → 4(B) → 3(D) → 6(C) → 5(E) → 2(F) → 0
となることから、要素6の次が要素5、要素6の前が3、つまり
　　next[6] = 5　prev[6] = 3
となります。

資格部