链表：一节一节连起来

数组要一整块连续的内存，链表不用：每个结点自己存一个数，再存一个指针 next 指向下一个结点，最后一个结点的 next 是 NULL。

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

struct node {
    int data;
    struct node *next;
};

int main(void)
{
    struct node *head = NULL, *p, *q;
    int i;
    for (i = 1; i <= 3; i++) {
        p = (struct node *)malloc(sizeof(struct node));
        p->data = i * 10;
        p->next = head;
        head = p;
    }
    for (p = head; p != NULL; p = p->next)
        printf("%d ", p->data);
    printf("\n");
    p = head;
    while (p != NULL) {
        q = p->next;
        free(p);
        p = q;
    }
    return 0;
}

• struct node *next;：结构体里放一个指向同类结构体的指针，结点就能一个接一个连起来。
• malloc(sizeof(struct node))：向系统要一个结点大小的内存（第 ⑤ 条路线学过），用完要 free。
• p->next = head; head = p;：新结点指向原来的第一个，再让 head 指向新结点——这叫头插法，新来的排最前。
• for (p = head; p != NULL; p = p->next)：从 head 出发，一步步往后走，走到 NULL 就停——这叫遍历。
• 释放时先用 q 记下 p->next，再 free(p)：p 已经还给系统了，就不能再读 p->next。

程序输出【0】；建好的链表里，最后一个结点的 next 是【1】；释放时如果把 q 去掉，写成 free(p); p = p->next;，【2】。