構造体+mallocで作る簡単な連結リスト

導入

配列は「後から個数を増やす」のが苦手です（レッスン32の realloc はコピーが発生することもあります）。構造体に「次の要素へのポインタ」を持たせ、malloc で1個ずつノードを作ってつなぐと、要素をいくつでも自由に追加できる連結リストになります。

説明

ノードは「値」と「次のノードへのポインタ」を持つ構造体です。ポインタが指す構造体のメンバには . ではなく ->（アロー演算子）でアクセスします。p->value は (*p).value と同じ意味です。

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int value;
    struct Node *next;
} Node;

int main(void) {
    Node *head = malloc(sizeof(Node));
    head->value = 1;
    head->next = malloc(sizeof(Node));
    head->next->value = 2;
    head->next->next = malloc(sizeof(Node));
    head->next->next->value = 3;
    head->next->next->next = NULL;   // 最後のノードの next は NULL（終わりの印）

    Node *cur = head;
    while (cur != NULL) {
        printf("%d\n", cur->value);
        cur = cur->next;             // 次のノードへ進む
    }

    cur = head;                      // たどりながら1個ずつ解放する
    while (cur != NULL) {
        Node *next = cur->next;      // 先に next を覚えておく（解放後は読めなくなるため）
        free(cur);
        cur = next;
    }
    return 0;
}

flowchart LR
  head["head"] --> n1["Node 1<br/>value=1"] --> n2["Node 2<br/>value=2"] --> n3["Node 3<br/>value=3"] --> nil["NULL（終わり）"]

解放するときに Node *next = cur->next; を先に読んでおくのがポイントです。もし free(cur); を先にしてしまうと、その後で cur->next を読むのはレッスン34で見たダングリングポインタになってしまいます。

やってみよう

ノードをもう1つ増やして4個つないでみましょう。head->next->next->next->next = NULL; を書き忘れると、while ループがどこで止まるべきか分からなくなることも確かめてください。

演習

値が 10, 20, 30, 40 の4つのノードをつないだ連結リストを作ってください。先頭から順に cur->value を1行ずつ表示し、たどりながら合計も計算して、最後に printf("合計=%d\n", sum); の形で表示してください（正しく書けると 10, 20, 30, 40, 合計=100 の5行になります）。最後は全ノードをきちんと free してください。