双方向リストに挿入するとどのポインタが変わる？
基本情報技術者試験 令和5年度 問2 ／ アルゴリズムとプログラミング › データ構造
過去問にチャレンジ
双方向のポインタをもつリスト構造のデータを表に示す。この表において新たな社員G を社員A と社員K の間に追加する。追加後の表のポインタa ～ f の中で追加前と比べて値が変わるポインタだけを全て列記したものはどれか。
- ア
a，b，e，f
- イ
a，e，f
- ウ
a，f
- エ
b，e
会話形式の解説
講師まず、表の行順ではなく、次ポインタが指す先をたどって挿入位置を確かめます。
受験者表ではTがKより上にありますが、Aの次はアドレス300なので、つながる先はKですね。
講師そうです。Kの次はアドレス200のTですから、挿入前はA、K、Tの順です。
受験者GをAとKの間に入れるなら、G自身は前にA、次にKを指すようにしますか。
講師はい。Gの前ポインタを100、次ポインタを300にします。では、既存の社員側ではどこを変えますか。
受験者Aの次ポインタとKの前ポインタを、Gのアドレス400に変えます。
講師その二つです。Aの次を表すaは300から400へ、Kの前を表すfは100から400へ変わります。
受験者Aの前を表すbや、Kの次を表すeはどうでしょうか。
講師Aの前は引き続き0、Kの次は引き続き200です。Tとのつながりも変わらないので、Tの二つのポインタも元の値のままです。
受験者すると、a、b、e、fを挙げるものはbとeが余分で、a、e、fを挙げるものもeが余分ですね。
講師はい。bとeだけを挙げるものは、変わらない二つを選び、必要なaとfを含んでいません。正解はaとfを挙げるウです。
受験者新しいGのポインタを設定することと、既存の表で値が変わるポインタを数えることは、分けて考えます。
講師その考え方です。挿入位置はアドレスの大小や行順ではなく、ポインタが示す前後関係で判断します。
まとめ
追加前の並びは、次ポインタをたどるとA、K、Tです。GをAとKの間に挿入すると、既存のAの次ポインタaとKの前ポインタfが、どちらもGのアドレス400に変わります。ほかの既存ポインタの値は変わらないため、正解はウです。
解答・解説
正解はウです
この問題のテーマ
双方向リストに要素を挿入するとき、既存のどのポインタを書き換えるかを問う問題です。
解き方の考え方
表の次ポインタをたどると、追加前は社員A、K、Tの順です。社員GをAとKの間に置くには、AからGへ、GからKへ進めるようにします。逆向きにもKからGへ、GからAへ戻れるようにして、追加前の値と比較します。
選択肢ごとの解説
- ×ア a，b，e，fアはa、b、e、fを変更対象としています。Aの前を示すbは0のままで、Kの次を示すeも200のままなので、余分なポインタを含んでいます。
- ×イ a，e，fイはa、e、fを変更対象としています。GをKの手前に入れても、Kの次にいるTとのつながりは変わらないため、eは変更しません。
- ○ウ a，fウが挙げるaとfは、挿入位置を挟むAの次ポインタとKの前ポインタです。どちらも元の相手のアドレスからGのアドレス400に変わるため、変更対象はこの二つです。
- ×エ b，eエはbとeを挙げていますが、どちらもGを挿入する位置には向いていません。実際には両方とも値が変わらず、変更が必要なポインタも挙げられていません。
POINT
- 次ポインタと前ポインタは、それぞれ別の向きのつながりを表します。
- 挿入位置は、アドレスの大小や表の行順ではなく、ポインタが指す先から判断します。
- 新しい要素自身のポインタの設定と、既存のポインタの変更は分けて数えます。