サンプル問題科目B 問10 - 基本情報技術者試験問題を解いてみる

問題

次のプログラム中の [ ] に入れる正しい答えを，解答群の中から選べ。

手続 delNode は，単方向リストから，引数 pos で指定された位置の要素を削除する手続である。引数 pos は，リストの要素数以下の正の整数とする。リストの先頭の位置を 1 とする。

クラス ListElement は，単方向リストの要素を表す。クラス ListElement のメンバ変数の説明を表に示す。ListElement 型の変数はクラス ListElement のインスタンスの参照を格納するものとする。大域変数 listHead には，リストの先頭要素の参照があらかじめ格納されている。

出典：基本情報技術者試験サンプル問題

図を描いてみる

リストの問題は、面倒くさがらずに図を描いてみるのが一番だと思います。

先頭の要素を削除した場合

まずは初期状態を描きます。ここでは4個の要素からなるリストを作りました。

このリストの先頭の要素を削除した場合を示します。プログラムでも「posが1と等しい」場合を特別扱いしています。

この場合はlistHeadがリストの2番目の要素を参照するように書き換えればOKです。2番目の要素の参照は、1番目の要素のnextフィールドに書いてあるので、それをlistHeadにコピーするだけです。

元々の1番目の要素はメモリ上には残りますが、listHeadからたどるリストから削除されたのでこれで完了です。実際には、削除した要素のメモリはそのうちガベージコレクションで回収されるはずです。

2番目の要素を削除した場合

2番目以降の要素を削除するには、listHeadをprev変数にコピーして、このprevを使ってリストをたどっていきます。

ただし2番目の要素の場合、プログラムにもコメントで「posが2と等しいときは繰り返し処理を実行しない」とあるように、リストをたどる必要はありません。

prevが参照する要素のnextを、3番目の要素を参照するよう書き換えるだけです。この書き換えが今回の問題です。

2番目の要素のnextの値が3番目を参照していて、これを1番目の要素のnextにコピーします。2番目の要素はprev.nextで参照で、そのnextフィールドをコピーするので、prev.next.nextが右辺にきます。(prev.next).nextと書いた方がわかりやすいかも知れません。解答群のカが答えですね。