連結リストを組み立てる ― 構造体とmallocの総合演習

導入

第7章の構造体と、第8章の malloc／free を組み合わせると、実行中に必要な数だけノードを増やせる「連結リスト」を自分の手で組み立てられます。ここでは、追加（append）・表示（print）・先頭削除（delete）の3つの操作をひとつのプログラムにまとめて、動くところまで作ります。

説明

連結リストの1つ分の要素をノードと呼びます。ノードは「値」と「次のノードへのポインタ」を持つ構造体です。最後のノードの next は、もう次がないことを表す NULL にします。

flowchart LR
  head["head（先頭を指すポインタ）"] --> n1["Node<br/>value=10<br/>next→"]
  n1 --> n2["Node<br/>value=20<br/>next→"]
  n2 --> n3["Node<br/>value=30<br/>next→"]
  n3 --> n4["Node<br/>value=40<br/>next→"]
  n4 --> nul["NULL（終わりの印）"]

ノードを作る・末尾に追加する・全件表示する・先頭を削除する・すべて解放する、という5つの関数に処理を分けて実装します。append と delete_first は「head そのもの（どのノードが先頭か）」を書き換える必要があるので、head のアドレス（Node **、ポインタのポインタ）を受け取ります。

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

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

// 新しいノードをmallocで確保して作る
Node *create_node(int value) {
    Node *node = (Node *)malloc(sizeof(Node));
    node->value = value;
    node->next = NULL;
    return node;
}

// リストの末尾に値を追加する（headを書き換えることがあるので Node** で受け取る）
void append(Node **head, int value) {
    Node *new_node = create_node(value);
    if (*head == NULL) {
        *head = new_node;
        return;
    }
    Node *cur = *head;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    cur->next = new_node;
}

// 先頭から辿って全件表示する
void print_list(Node *head) {
    Node *cur = head;
    while (cur != NULL) {
        printf("%d ", cur->value);
        cur = cur->next;
    }
    printf("\n");
}

// 先頭のノードを1つ削除する
void delete_first(Node **head) {
    if (*head == NULL) return;
    Node *old_head = *head;
    *head = old_head->next;
    free(old_head);
}

// 残っているノードをすべて解放する
void free_list(Node *head) {
    Node *cur = head;
    while (cur != NULL) {
        Node *next = cur->next;
        free(cur);
        cur = next;
    }
}

int main(void) {
    Node *head = NULL;

    append(&head, 10);
    append(&head, 20);
    append(&head, 30);
    append(&head, 40);

    printf("追加後: ");
    print_list(head);          // 10 20 30 40

    delete_first(&head);

    printf("先頭を削除後: ");
    print_list(head);          // 20 30 40

    free_list(head);           // 使い終わったら必ず全部解放する

    return 0;
}

いくつか押さえておきたい点があります。

• append(&head, 10) の &head は「head という変数そのものの場所」です。append の中で *head = new_node; と書くことで、呼び出し元の head を直接書き換えられます。もし Node *head のまま受け取ると、関数の中だけのコピーを書き換えることになり、呼び出し元には反映されません。
• free_list で全部解放したあとの head は、指す先が解放済みのメモリになっています（ダングリングポインタ）。この後うっかり使わないよう、実務では解放後に head = NULL; としておくのが安全です。
• 一度 free したノードを、リストからつなぎ直す前にもう一度 free してしまう（二重解放）や、free し忘れる（メモリリーク）は、C でよく起きるバグです。「1つ malloc したら、どこかで必ず1回だけ free する」を徹底しましょう。

やってみよう

上のコードを実行し、追加・削除でリストの中身がどう変わるか確かめましょう。append(&head, 50); をもう1行足したり、delete_first(&head); をもう1回呼んだりして、表示がどう変わるか試してください。

演習

値 1, 2, 3, 4, 5 を持つ5つのノードを連結リストに追加してください。次に delete_first を2回呼んで先頭の2件（1 と 2）を削除し、残ったリストを リスト: に続けて表示し、続けて残りの値の合計を 合計= に続けて表示してください（結果は リスト: 3 4 5 と 合計=12）。