ノードを定義する｜コードで実践

自分と同じ型を指すポインタ

連結リストの部品を、ここではノードと呼びます。ノードは「1人分の値」と「次はこれ」という矢印を1本ずつ持ちます。学生1人分ならこうです。

struct Node {
    char name[32];
    int score;
    struct Node *next;
};

要点は next の型です。定義している途中の struct Node を、その定義の中で使っています。これを自己参照構造体と呼びます。

なぜこれが書けるのかというと、next はノードそのものではなくポインタだからです。コンパイラは構造体の大きさを決めるために各メンバの大きさを足しますが、ポインタの大きさは指す先の中身と関係なく決まっています。だから struct Node の中身がまだ確定していなくても計算が止まりません。

struct Node {
    struct Node next;   /* これは通らない */
};

こちらは自分の大きさを求めるのに自分の大きさが要るので、決めようがありません。ノードをつなぐ矢印がポインタでなければならない理由は、書き方の作法ではなく、これです。

ノードはヒープに作る

ノードは、プログラムが動いている途中で1個ずつ増えていきます。何個できるかは実行してみるまで分かりません。前章で見たとおり、こういう相手はヒープに置きます。

struct Node *first = malloc(sizeof(struct Node));

sizeof(struct Node) はノード1個分の大きさです。sizeof(struct Node *) と書くとポインタ1個分しか確保できないので、* の有無をここで間違えると、名前を書き込んだ時点で隣を壊します。

確保したノードは、free を呼ぶまで生き続けます。関数を抜けても消えないという性質が、あとで「関数の中で作ったノードを呼び出し元へ返す」という書き方を支えます。

つなぐのは代入1つ

矢印を張るのは代入です。

first->next = second;
second->next = NULL;

first->next は (*first).next の省略形で、入門で見たとおりの記法です。最後のノードの next には NULL を入れます。これがリストの終わりの印になり、歩くときの止まる条件になります。

矢印を入れ忘れたときに起きること

next に何も入れないまま歩き始めると、そこには malloc が返した時点の中身、つまり意味のない値が残っています。その値をアドレスとみなして参照した瞬間にプログラムは落ちるか、もっと悪いことに落ちずに知らない場所を読み書きします。ノードを作ったら、値を入れるのと同じ手で next も必ず決める、という手順にしておくと、この事故は起きません。あとで書く追加関数を、確保から next の設定までを1か所に閉じ込めた形にするのは、そのためでもあります。

では、ノードを2つ作って手でつないでみましょう。

ノードを定義する

自分と同じ型を指すポインタ

ノードはヒープに作る

つなぐのは代入1つ

矢印を入れ忘れたときに起きること

要件

入出力例

ヒント

メモ