単方向リストのメモ

はじめに

単方向リスト（リンクリスト） というデータ構造を使って、
入力したデータを「前に追加」していく仕組みを実現する例のメモ。
（だから最後に表示すると、入力順が逆になります。）

1. 構造体の定義

typedef struct st_num {
    struct st_num *next;  // 次のデータへのポインタ
    int data;             // 自分のデータ
} NUM;

• NUM という構造体を定義
• 各ノードは data と「次のノードへのポインタ next」を持つ
  → これが「鎖の1つの輪っか」みたいなイメージ

2. main の変数

NUM *top = NULL;   // リストの先頭を指す
NUM *p;            // 作業用ポインタ

• top が リストの頭を示すポインタ
• p は 新しく確保したノードを操作するためのポインタ

3. データ入力ループ

while (1) {
    scanf("%d", &x);
    if (x == 0) break;

    p = (NUM *)malloc(sizeof(NUM));  // 新しいノード確保
    p->next = top;                   // 今の先頭を次に繋げる
    top = p;                         // 先頭を新しいノードに更新
    p->data = x;                     // 入力データを格納
}

• malloc でノードを作る
• p->next = top; で「今までのリスト」を新しいノードの後ろにつなげる
• top = p; で「新しいノード」を先頭にする
  → これで「前に追加」されていく。

例）入力順が 1 → 2 → 3 の場合：

入力1:  top → [1]
入力2:  top → [2] → [1]
入力3:  top → [3] → [2] → [1]

4. 表示部分

p = top;
while (p) {
    printf("%d\n", p->data);
    p = p->next;
}

• 先頭から順番に辿りながら data を出力
• 入力が 1,2,3 なら出力は 3,2,1

5. メモリ解放

p = top;
while (p) {
    printf("%d\n", p->data);
    NUM *tmp = p;
    p = p->next;
    free(tmp);   // 使い終わったノードを解放
}

「入力した整数をリンクリストに前から追加して、最後に全部出力するプログラム」
→ 出力が逆順になるのは「前に追加」しているから。

コード例

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

typedef struct st_num {
    struct st_num *next;
    int data;
} NUM;

int main(void)
{
    int x;
    NUM *top = NULL;  /* 先頭ノード */
    NUM *p;

    while (1) {
        printf("data('0'入力で終了) = ");
        if (scanf("%d", &x) != 1) {   /* 入力失敗対策 */
            fprintf(stderr, "入力エラー\n");
            break;
        }
        if (x == 0) break;            /* 終了 */

        p = (NUM *)malloc(sizeof(NUM));   /* Cではキャスト不要だが、一応残す */
        if (p == NULL) {
            fprintf(stderr, "メモリ確保に失敗しました\n");
            /* ここまでに確保済みノードを全解放して終了 */
            for (NUM *q = top; q != NULL; ) {
                NUM *tmp = q;
                q = q->next;
                free(tmp);
            }
            return 1;
        }

        p->next = top;  /* 先頭挿入：新ノードの next に現在の先頭をぶら下げる */
        p->data = x;    /* データ格納 */
        top = p;        /* 先頭更新 */
    }

    /* 表示しながら全ノードを解放 */
    p = top;
    while (p) {
        printf("%d\n", p->data);
        NUM *tmp = p;
        p = p->next;
        free(tmp);
    }

    return 0;
}

• 入力が 1, 2, 3, 0 のとき出力は 3, 2, 1（先頭挿入なので逆順）。
• 最後の while で 表示 → 次へ進む → 直前ノードを free の順にして、漏れなく解放。
• 途中で malloc が失敗した場合も、それまで確保した分を全て解放してから終了。