応用情報技術者試験 令和5年度 秋期 午前 問5

【正解】ウ

図のnextをHead＝1からたどると、要素番号は1→4→3→5→2→0です。elemの値を対応させると、現在のリストはA→B→D→E→Fとなります。Dの要素番号は3であり、その直後のEの要素番号は5です。新しい要素は一次元配列の末尾へ追加するため、Cの要素番号は6になります。挿入後はA→B→D→C→E→Fとなるので、Cから見た次の要素はE、前の要素はDです。したがって、next[6]＝5、prev[6]＝3となり、ウが正解です。併せて、DからCへつなぐnext[3]＝6と、EからCへ戻るprev[5]＝6への更新も必要です。

アは誤りです。prev[6]＝3はDを前の要素とするので正しいですが、next[6]＝2ではCの次がFとなり、本来間にあるEを飛ばしてしまいます。

イは誤りです。next[6]＝3、prev[6]＝4は、Cを要素番号4のBと要素番号3のDの間に置く設定です。これはDの次ではなく、Dの前への挿入になります。

エは誤りです。next[6]＝5によってCの次をEとする点は正しいですが、prev[6]＝4ではCの前がBになります。Dの要素番号は3なので、双方向の連結関係が一致しません。

【ポイント】 双方向リストへの挿入では、新要素のnextとprevだけでなく、前後の既存要素のリンクも更新します。 挿入位置の前をp、後ろをq、新要素をnとすると、next[p]＝n、prev[n]＝p、next[n]＝q、prev[q]＝nです。 配列上の要素番号の順序と、リスト上の並び順は同じとは限りません。