リストを歩く｜コードで実践

何番目、では取り出せない

前回で追加ができるようになりました。今度は中身を全部見る番です。

配列なら for (i = 0; i < n; i++) で list[i] を順に見ました。リストにはその添字がありません。2人目がどこにいるかは、1人目の next を読むまで分からないからです。ノードは malloc が空いている場所へ置いていくので、番地の並びと順番は無関係です。並び順を持っているのは矢印だけです。

歩く形はいつも同じ

そこで、ポインタを1本用意して、矢印をたどって進めます。

struct Node *p;
for (p = head; p != NULL; p = p->next) {
    printf("%s %d点\n", p->name, p->score);
}

初期化が p = head、続ける条件が p != NULL、更新が p = p->next です。この3つは配列の i = 0 と i < n と i++ にそのまま対応します。リストを歩くコードはほぼ全部この形になるので、指の形として覚えてしまってよいところです。

止まる条件が p != NULL になるのは、最後のノードの next に NULL を入れてあるからです。終端の印を決めておいたことが、ここで効きます。

head そのものを動かさない

やりがちな間違いは、作業用のポインタを用意せずに head を進めてしまうことです。

while (head != NULL) {
    printf("%s\n", head->name);
    head = head->next;   /* 呼び出し元の先頭が失われる */
}

関数の引数として受け取った head なら、動かしても写しなので呼び出し元は無事です。しかし同じ癖で main の head を進めると、表示が終わったときリストの先頭がどこにも残っておらず、全ノードが解放できないまま迷子になります。歩くときは必ず別のポインタを使う、と決めておくと安全です。

数えるのも足すのも同じ歩き方

人数を数える、点数を合計する、特定の名前を探す。どれも歩き方は同じで、ループの中で何をするかが違うだけです。探索の場合は見つけた時点で return p; すれば途中で止められます。

歩く回数は積み上がる

気をつけたいのは、歩くこと自体は人数に比例した手間だという点です。表示のたびに人数を数え直し、合計も数え直し、その中でまた探索を呼ぶ、という書き方をすると、1回の操作で何度もリスト全体を往復します。人数が少ないうちは気づきませんが、これは配列で詰め直しをしていたときと同じ種類の重さです。

対策は難しくありません。1回の歩きで済むものは1回にまとめる、人数のように変化が分かっているものは追加と削除のときに増減させて持っておく、といった程度です。今回は素直に別々の関数として書きますが、「この関数は先頭から終端まで1往復する」という感覚は持っておいてください。

では、一覧表示と合計点の2つを、同じ歩き方で書いてみましょう。

リストを歩く