データ構造(全39問中1問目)
No.1解説へ
双方向リストを三つの一次元配列 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
広告
解説
双方向リストは、前の要素への参照と後ろの要素への参照を持ち、先頭からも末尾からも要素をたどることができるリスト構造です。
3つの配列を見ると、現在のリストは先頭（Head）が要素番号1のA、2番目が要素番号4のB、同様にD、E、Fというように連結されていることがわかります。
Cはリスト上のDとEの間に挿入されるので、CのnextにはEが格納されている要素番号5、CのprevにはDが格納されている要素番号3を設定しなければなりません。Cは一次元配列の末尾である要素番号6に追加されるので、next[6] = 5、prev[3] = 3 となります。
したがって「ウ」の組合せが正解です。
3つの配列を見ると、現在のリストは先頭（Head）が要素番号1のA、2番目が要素番号4のB、同様にD、E、Fというように連結されていることがわかります。