STAGE 8
総合稽古
リストから1つ消す関数を完成させる
🎯 ミッション
deleteNode の3か所の穴を埋め、先頭を消す場合と途中を消す場合の両方を説明できるようになろう。完成したコードを最後の行まで実行し、確認クイズに全問正解すれば合格。
未達成

ねこ博士
最後の稽古だ。連結リストから、値が value のノードを1つ取り外して返す関数
deleteNode を完成させる。STAGE6 の最後で、きみが言ったことを覚えているかな。
うさ美
先頭を消すときは head を書き換えないといけない。head は main の変数だから、関数には head の番地を渡す。だから引数は Node ** です。

ねこ博士
そう。呼ぶときは
deleteNode(&head, 2); のように書く。関数の骨組みはこうだ。void deleteNode(Node **headRef, int value) {
Node *cur = *headRef; // 先頭から
Node *prev = NULL; // 1つ手前(最初はいない)
while (cur != NULL && cur->value != value) {
prev = cur;
cur = cur->next;
}
if (cur == NULL) return; // 見つからなかった
if (prev == NULL) {
【穴1】 // 先頭を消す
} else {
【穴2】 // 途中か最後を消す
}
【穴3】 // 取り外したノードを返す
}
&& は「かつ」。cur が NULL でなく、かつ値が違う間、前へ進む

うさ美
くり返しが終わったとき、cur は消したいノード、prev はその1つ手前。prev が NULL なのは、手前がいない、つまり cur が先頭のとき。

ねこ博士
その通り。3つの穴を埋める考え方は、どの場合も「消すノードを飛ばして、その次へつなぐ」ことだ。先頭なら、飛ばす元は誰かな。

うさ美
先頭の手前にはノードがないから……飛ばす元は head そのものですね。head を cur の次に向ける。head を書き換えるには *headRef。途中なら、手前の prev の next を、cur の次に向ける。

ねこ博士
そう。穴を埋めた完成版で、3つのノード 1 → 2 → 3 から 2 を消す様子を見ておこう。

うさ美
もし先頭の 1 を消していたら、prev は NULL のままで、*headRef = cur->next によって main の head が 2 に向け直される。関数が終わっても head の書き換えは残る……。STAGE5 の allocate と同じ仕組みです。

ねこ博士
よくここまで来たね。番地、配列、ヒープ、構造体、ポインタのポインタ、リスト、間違いの見抜き方。C言語のポインタで使う道具は、これで一通りそろった。
& で番地を取り、* で番地の先へ。ポインタも番地付きの箱(8バイト)
配列の名前は先頭の番地に変わる(sizeof と & は例外)。a[i] = *(a+i)
malloc → NULL を確かめる → 使う → free → NULL を入れる
-> は (*p).メンバ。構造体にはすき間(パディング)が入りうる
引数はコピー。書き換えたいものの番地を渡す(ポインタなら **)
返したもの・範囲の外・でたらめな番地・NULL を使うのは未定義動作
確認クイズ
Q1. 【穴1】先頭のノードを消すとき(prev が NULL)に入る正しい処理は?
正解! 書き換えたいのは main の head そのもの。headRef は head の番地なので、*headRef に代入して初めて head が変わる。headRef = … では関数の中のコピーが変わるだけ。
Q2. 【穴2】途中か最後のノードを消すときに入る正しい処理は?
正解! 手前のノード prev の next を、消すノードの次へつなぎ替える。これで cur はリストから外れる。
Q3. 【穴3】最後に入る正しい処理は?
正解! 取り外しただけではヒープの場所は返らない。free(cur) で返す。headRef はスタックの head の番地なので、free してはいけない。