こんにちは、おゆかよです。
この記事では、双方向リストの仕組みと、要素の挿入によって配列の状態がどう変化するのかを図を使って理解できます＾＾
前回の記事：
問題と解答の確認
出典：応用情報技術者試験 令和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である要素は、それぞれ双方向リストの末尾、先頭を表す。
- 双方向リストへの要素の追加は、一次元配列の末尾に追加
選択肢：
ア：next[6]=2, prev[6]=3
イ：next[6]=3, prev[6]=4
ウ：next[6]=5, prev[6]=3
エ：next[6]=5, prev[6]=4
正解： ウ
双方向リストって何？
博士〜！双方向リストって、次と前を両方覚えてるリストってことだよね？でも「Dの次にCを挿入」って…どこをどう変えたらいいのか混乱してきたよ！
双方向リストは next で次の要素を、prev で前の要素を記録してるんだ。
今回のリストの状態を見てごらん。
「要素 D」っていうのは elem[3] で、次は 5（つまり E）、前は 4（つまり B）になってるね。
そうだね！このDの次、つまり next[3] = 5 のところに「C」を挿入するんだ。
新しい要素Cは 要素番号6 だね。
じゃあ、next[3] は 6 になって、prev[6] は 3？？
正解！さらに、C の後ろには E（要素5）が来るから、next[6] = 5、Eの prev[5] = 6 に変える必要があるよ。
なるほど！つまり：
next[3] = 6（D→C）prev[6] = 3（C←D）next[6] = 5（C→E）prev[5] = 6（E←C）
う、結果として next[6] = 5, prev[6] = 3 になる組み合わせを選べばOKだよ。
それって「ウ」の選択肢だね？
その通り、正解は「ウ」だよ！
最後にもう一度、問題と解答を見てみよう
出典：応用情報技術者試験 令和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である要素は、それぞれ双方向リストの末尾、先頭を表す。
- 双方向リストへの要素の追加は、一次元配列の末尾に追加
選択肢：
ア：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とprevをすべて更新する必要がある - 今回は D の次に C を追加したので、C の前は D（要素3）、次は E（要素5）
- よって、
next[6] = 5,prev[6] = 3→ 正解は「ウ」
次の記事：
コメント