単方向リストの削除は、要素を消すことではありません。消す要素を指している向き先を、その次へ付け替えること。それが読めれば、空欄は1つに決まります。
難易度 ★★（当サイトの目安）── 「1つ先を飛ばしてつなぎ直す」処理だと分かれば決まる。4段階の決め方は科目B 最短合格の戦略にあります。
出題
出典：基本情報技術者試験 科目B サンプル問題 問10
次のプログラム中の に入れる正しい答えを，解答群の中から選べ。
手続delNode は，単方向リストから，引数pos で指定された位置の要素を削除する手続である。引数pos は，リストの要素数以下の正の整数とする。リストの先頭の位置を1 とする。
クラスListElement は，単方向リストの要素を表す。クラスListElement のメンバ変数の説明を表に示す。ListElement 型の変数はクラスListElement のインスタンスの参照を格納するものとする。大域変数listHead には，リストの先頭要素の参照があらかじめ格納されている。
表 クラスListElement のメンバ変数の説明
| メンバ変数 | 型 | 説明 |
|---|---|---|
val |
文字型 | 要素の値 |
next |
ListElement |
次の要素の参照 次の要素がないときの状態は未定義 |
〔プログラム〕
大域: ListElement: listHead // リストの先頭要素が格納されている
○delNode(整数型: pos) /* posは，リストの要素数以下の正の整数 */
ListElement: prev
整数型: i
if (pos が 1 と等しい)
listHead ← listHead.next
else
prev ← listHead
/* posが2と等しいときは繰返し処理を実行しない */
for (i を 2 から pos － 1 まで 1 ずつ増やす)
prev ← prev.next
endfor
prev.next ←
endif
解答群
ア listHead ／ イ listHead.next ／ ウ listHead.next.next
エ prev ／ オ prev.next ／ カ prev.next.next
※ 解答群の原本は ア〜カ を2つの列に分けて並べた形です。当サイトでは2行にまとめて引用しました（字句は変えていません）。
答えだけ先に見る
正解は カ（prev.next.next）です。
この問題に出てくる記号
読めない記号があったときだけ開いてください。このあとプログラムを読む場面で詰まったら、ここへ戻ってきてください。
擬似言語の記号 7コ の読み方をひらく
| 書き方 | 読み方 |
|---|---|
| 参照／インスタンス | 「インスタンス」＝作られた要素1つ、「参照」＝その要素そのものではなくどの要素かを指すもの。listHead や next 欄に入っているのが、これです |
大域: ListElement: listHead |
どの手続からも見える変数。リストの先頭の要素を指しています |
ListElement: prev |
要素を指すための箱。入るのは値そのものではなく「どの要素か」です |
prev.next |
prev が指している要素の next 欄。そこに次の要素が入っています（次が無いときは未定義） |
prev.next.next |
prev.next が指している要素の、さらに next 欄。.next は続けて書けます（1つ書くごとに1つ先へ進む） |
prev ← prev.next |
prev の指す先を、1つ次の要素へ移す |
prev.next ← ○○ |
prev が指している要素の next 欄を、○○ に書き換える（prev 自身は動きません） |
for (i を 2 から pos － 1 まで 1 ずつ増やす) |
i を 2 から pos － 1 まで。pos が 2 なら上限が 1 になり、下限の 2 より小さいので1回もまわりません |
/* … */ // … |
注釈。読む人への説明で、実行には関係ありません |
コードは何をしているか ── 「削除」は、向き先の付け替え
どの行が何をしているかを、先に見ておきます。
○delNode(整数型: pos)
消す位置 pos を受け取る。返す値はない
ListElement: prev
要素を指すための箱。else の側でだけ使う
整数型: i
くり返しの回数を数える箱
if (pos が 1 と等しい)
先頭を消す場合
listHead ← listHead.next
先頭を指していた listHead を、その次へ向け直す
else
2番目より後ろを消す場合
prev ← listHead
prev を先頭から始めて…
for (i を 2 から pos － 1 まで 1 ずつ増やす)
prev ← prev.next
…next を1つずつたどって進める
endfor
prev.next ←
？ ここでも向き先を付け替える
endif
※ 右側の注釈は当サイトで書き加えたものです。プログラム自体は原文のまま引用しています。
この手続は値を返しません。書き換えているのは、要素どうしのつながりだけです。そして、そのやり方は pos が 1 のときの行にそのまま出ています。listHead ← listHead.next ── 先頭を消すというのは、先頭を指していた listHead を、その次へ向け直すことでした。消した要素そのものを消す行は、どこにもありません。
単方向リストの削除は、消す要素を指している向き先を、その要素の次へ付け替えることです。else のほうでも、やることは同じです。ちがうのは誰が消す要素を指しているかだけ。それを確かめるために、まず prev がどこまで進むかを見ます。
prev はどこで止まるか
空欄は else の側にあるので、pos が 1 のときは通りません。通る中でいちばん小さいのは pos が 2 ですが、そのときは注釈のとおり for が1回もまわらず、prev は listHead に置かれたきり動きません。prev が動くところまで見えるいちばん小さい場合が、pos ＝ 3 です。要素が4つ（val が A・B・C・D）のリストで delNode(3) を呼び、3番目の C が消えるまでを追います。
delNode(3) を動かすと、prev はどこで止まるか
箱＝リストの要素／かっこの中＝その要素を指している変数／琥珀の枠＝いま prev が指している要素
① else に入って、prev を先頭に置いたところ
prev ← listHead
A
（listHead・prev）
B
C
D
prev は listHead と同じ、1番目の A を指しています。
② for を1回まわったあと
for (i を 2 から pos － 1 まで 1 ずつ増やす)
prev ← prev.next
A
（listHead）
B
（prev）
C
D
pos は 3 なので上限は 3 － 1 ＝ 2。i は 2 から始まるので1回だけまわり、prev は next を1つたどって2番目の B へ移ります。listHead は動きません（動かす行がありません）。
消したい3番目の C から見ると、prev はその1つ前にいます。
pos ＝ 3 以外でも同じです。prev は listHead（1番目）から始まり、for が1回まわるごとに1つ先へ進みます。まわる回数は i が 2 から pos － 1 までの pos－2 回なので、止まるのは 1 ＋（pos－2）＝ pos－1 番目。消すのは pos 番目なので、for を抜けたとき prev は消す要素のちょうど1つ前にいます。だから prev.next が、消す要素そのものです。
空欄に入れるものを決める
〔プログラム〕空欄のまわり（上の〔プログラム〕から抜き出した。1字も変えていない）
prev ← listHead
/* posが2と等しいときは繰返し処理を実行しない */
for (i を 2 から pos － 1 まで 1 ずつ増やす)
prev ← prev.next
endfor
prev.next ←
※ 上の〔プログラム〕からの抜粋です（1字も変えていません）。
空欄の行は prev.next ← です。書き換わるのは prev が指している要素の next 欄 ── 消す要素の1つ前の、行き先です。では、どこへ向ければよいか。
3番目の C を消すと、つながりはどうなってほしいか
箱＝リストの要素／かっこの中＝その要素を指している変数／琥珀の枠＝いま prev が指している要素／灰＝先頭からたどり着けなくなった要素
いまのつながり
A
（listHead）
B
（prev）
prev.next
C
D
消したいのは3番目の C。いま C を指しているのは、prev の next 欄です（矢印に名前を付けました）。
C を消したあと
A
（listHead）
B
（prev）
向け直す
D
どこからも指されなくなる要素：
C
先頭からたどると A → B → D。書き換えたのは B の next 欄1つだけです（C 自身も、C の next 欄が D を指したままなのも、変わりません）。C へ入る矢印が無くなったので、先頭からは C にたどり着けません。
prev の next 欄を、消す要素の次へ向け直す。空欄に入れるのは、この「消す要素の次」です。
消す要素は prev.next でした。ほしいのはその要素の next 欄なので、○○.next の ○○ のところに prev.next を置きます。つまり prev.next のうしろに .next をもう1つ足して、prev.next.next です。
解答群を見る
prev.next.next は カ です。
答え合わせ
正解は カ です。
ア・イ・ウ は listHead から数えた位置で、式に pos も prev も出てきません。pos がいくつでも同じ要素を指すので、どの pos でも正しく消せるはずがありません（ウ が当たるのは pos が 2 のときだけ、ア・イ はどの pos でも当たりません）。エ prev.next ← prev は、B の next 欄が B 自身を指すので、先頭からたどると A → B → B → B … と同じ要素をくり返し、C にも D にも進めません。オ prev.next ← prev.next は、いまと同じものを入れ直すだけで何も消えません。
カを入れて、A・B・C・D のリストで delNode(3) を最後まで動かします。
1行ずつ追う 正解の カ で delNode(3)（A・B・C・D の4要素）
出典：科目B サンプル問題 問10（当サイトで空欄に カ を入れ、注釈は ※ の1行に書き直しました）
ループ開始前
いま計算していること
変数の状態
出力
トレース表（進めると1行ずつ積み上がります）
次に読む
この問題でどこに手間取ったかで、行き先が変わります。
この記事で引用した資料
いずれも独立行政法人情報処理推進機構（IPA）が公表したものです。IPAは公表済みの試験問題について、教育目的での使用に許諾および使用料を不要としていますが、著作権は放棄していません。本記事では問題文を改変せずに引用しています。
