STAGE 6
連結リスト
ポインタでつなぐ鎖
🎯 ミッション
連結リストのつなぎ方・たどり方・返し方を説明できるようになろう。コードを最後の行まで実行し、確認クイズに全問正解すれば合格。
未達成

ねこ博士
配列は、要素が番地の連続した場所に並んでいた。だから、途中に1つ割り込ませたいときは、後ろを全部1つずつずらさないといけない。100万個並んでいたら大仕事だ。

うさ美
並びを入れ替えるたびに、全部を引っ越しさせるようなものですね。

ねこ博士
そこで、要素をヒープのばらばらの場所に置いて、それぞれに「次の要素の番地」を持たせるやり方がある。これを連結リストと呼ぶ。1つ1つの要素をノード(結び目)と呼ぶ。
typedef struct Node {
int value; // 中身
struct Node *next; // 次のノードの番地(最後なら NULL)
} Node;
構造体の中で自分と同じ型を指すポインタを使うので、名前を struct Node と2回書いている

うさ美
割り込ませたいときは、前のノードの next を新しいノードに向けて、新しいノードの next を元の次に向ければいい。ほかのノードは動かさなくていい。

ねこ博士
そう。つなぎ替えは2か所の書き換えで済む。その代わり、「5番目の要素」に行くには、先頭から next を5回たどらないといけない。配列なら番地の計算1回で行けたのにね。どちらが向いているかは、使い方次第なんだ。

うさ美
返すときに next を先に控えていたのは、free した後に cur->next を読むと、返した場所を読むことになるからですね。

ねこ博士
その通り。
free(cur); cur = cur->next; と順番を逆に書くと、解放後の使用になる。しかも多くの場合、返した直後は古い値が残っているので、たまたま動いてしまう。だから見つけにくいんだ。
うさ美
for の中で使った cur は、くり返しが終わると消えていました。

ねこ博士
for の () の中で宣言した変数は、そのくり返しの間だけ使える。だから、あとの while では別に cur を宣言し直している。

ねこ博士
連結リストの先頭のノードを消したいときは、何を書き換える必要があるかな。

うさ美
先頭を消したら、2つ目が新しい先頭になる。だから head を2つ目に向け直す。……head は main の変数だから、別の関数の中で先頭を消すなら、head の番地を渡さないといけない。STAGE5 の int ** と同じ形の、Node ** が要りますね。

ねこ博士
そう。それが最後の総合稽古で作る deleteNode のいちばん大事なところになる。その前に、ポインタでよくある間違いを道場で稽古しておこう。
確認クイズ
Q1. head->next = second; を実行すると、何が起きる?
正解! next はポインタなので、入るのは番地。これでノードからノードへたどれるようになる。
Q2. リストを全部返すときに、free(cur); の前に次の番地を控える理由は?
正解! 返した場所の中身を読むのは未定義動作。先に次の番地を別の変数に移しておく。
Q3. 連結リストが配列より得意なことは?
正解! 配列は途中に入れると後ろを全部ずらす必要がある。リストはつなぎ替えだけで済む。逆に、何番目かへ行くにはたどる必要があり、番地もばらばらでキャッシュに当たりにくい。