链表

第 26 课，共 30 课 · 第 5 部分 · 自己的类型 · 约 20 分钟

数组里的元素一个挨一个地排着。想在最前面加一个，后面的就得全往后挪一格；放不下了，还得 realloc 换一块更大的（第 22 课）。链表换了个思路：每一项单独放在一个小框里，叫节点；每个节点除了自己的值，还记着下一个节点在哪儿。要加一项，新建一个节点，改一两个指针就行，别的节点一动不动。

这一课用一张购物清单做例子。点单步的时候，链表会画成一串框，框和框之间用箭头连着。

节点

一个节点是一个结构体：一个成员放值，一个成员是指向下一个节点的指针。

main.c

1#include <stdio.h>2 3typedef struct node {4    char item[16];5    struct node *next;6} Node;7 8int main(void) {9    Node c = { "鸡蛋", NULL };10    Node b = { "面包", &c };11    Node a = { "牛奶", &b };12    Node *head = &a;13    for (Node *p = head; p != NULL; p = p->next) {14        printf("%s\n", p->item);15    }16    return 0;17}

输出

牛奶
面包
鸡蛋

点单步，看三个框怎么连起来：a 的 next 指向 b，b 的指向 c，c 的 next 是 NULL，表示到头了。head 指着第一个节点，有了它就能找到整串。

注意结构体里写的是 struct node *next，不能写 Node *next：读到这一行时，typedef 还没完，Node 这个名字还不存在。这就是上一课说的「结构体要用到自己时，花括号前面要写名字」。

走一遍

链表没有下标，不能写 list[2]。要找第三个，只能从 head 出发，顺着 next 一个一个走过去。上面的 for 就是走一遍链表的固定写法：

部分	意思
`Node *p = head`	从第一个节点开始
`p != NULL`	还没走到头就接着走
`p = p->next`	走到下一个节点

把它写成函数，就能显示整串、数一数有几个。函数拿到的是一个节点的地址，从哪个节点开始，就从哪里往后走：

main.c

1#include <stdio.h>2 3typedef struct node {4    char item[16];5    struct node *next;6} Node;7 8void print_list(Node *head) {9    for (Node *p = head; p != NULL; p = p->next) {10        printf("%s -> ", p->item);11    }12    printf("NULL\n");13}14 15int count(Node *head) {16    int n = 0;17    for (Node *p = head; p != NULL; p = p->next) {18        n++;19    }20    return n;21}22 23int main(void) {24    Node c = { "鸡蛋", NULL };25    Node b = { "面包", &c };26    Node a = { "牛奶", &b };27    print_list(&a);28    printf("一共 %d 样\n", count(&a));29    print_list(&b);30    return 0;31}

输出

牛奶 -> 面包 -> 鸡蛋 -> NULL
一共 3 样
面包 -> 鸡蛋 -> NULL

走过了头会怎样？清单只有两样，却想把第三样改成「鸡蛋」：

main.c

1#include <stdio.h>2#include <string.h>3 4typedef struct node {5    char item[16];6    struct node *next;7} Node;8 9int main(void) {10    Node b = { "面包", NULL };11    Node a = { "牛奶", &b };12    Node *head = &a;13    strcpy(head->next->next->item, "鸡蛋");14    return 0;15}

输出

store to null pointer

发生了什么： 停在第 13 行：这个指针是 NULL（空指针），不能通过它读写。

head->next 是 b，b 的 next 是 NULL，再 ->item 就是往 NULL 里写东西，可 NULL 不指向任何节点。我们的引擎停在这一行；真正的电脑上程序一般会崩溃。点「看看是怎么出错的」，顺着箭头走一遍，看最后一步落在了哪里。

在堆上建节点

上面的节点都是 main 里的局部变量，个数写死在代码里。真正用链表时，节点是程序跑起来以后一个一个建出来的，所以放在堆上。写一个函数专门建节点：

main.c

1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4 5typedef struct node {6    char item[16];7    struct node *next;8} Node;9 10Node *new_node(const char *item) {11    Node *n = malloc(sizeof(Node));12    if (n != NULL) {13        strcpy(n->item, item);14        n->next = NULL;15    }16    return n;17}18 19int main(void) {20    Node *a = new_node("牛奶");21    Node *b = new_node("面包");22    Node *c = new_node("鸡蛋");23    a->next = b;24    b->next = c;25    for (Node *p = a; p != NULL; p = p->next) {26        printf("%s\n", p->item);27    }28    free(a);29    free(b);30    free(c);31    return 0;32}

输出

牛奶
面包
鸡蛋

点单步：每调用一次 new_node，堆上多一个框，next 是 NULL。a->next = b; 这一步，一个箭头从第一个框连到第二个框上。最后三个 free 把三个框一个一个还回去。

小技巧： 为了让例子短一点，这一课有些地方没有检查 malloc 和 new_node 返回的是不是 NULL。真正的程序里要查。

全部 free 掉

节点多了，不能一个一个写 free，要走一遍链表来释放。最顺手的写法却是错的：

main.c

1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4 5typedef struct node {6    char item[16];7    struct node *next;8} Node;9 10Node *new_node(const char *item) {11    Node *n = malloc(sizeof(Node));12    if (n != NULL) {13        strcpy(n->item, item);14        n->next = NULL;15    }16    return n;17}18 19int main(void) {20    Node *head = new_node("牛奶");21    head->next = new_node("面包");22    for (Node *p = head; p != NULL; p = p->next) {23        free(p);24    }25    return 0;26}

输出

heap-use-after-free

发生了什么： 停在第 22 行：这块内存已经 free 了（还回去了），不能再用。

free(p) 之后，for 接着算 p = p->next：可 p 指的那个框刚刚已经还回去了，这就是用了已经 free 的内存（第 21 课）。引擎停在这一行，点「看看是怎么出错的」。

办法是：free 之前，先把下一个节点的地址存起来：

main.c

1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4 5typedef struct node {6    char item[16];7    struct node *next;8} Node;9 10Node *new_node(const char *item) {11    Node *n = malloc(sizeof(Node));12    if (n != NULL) {13        strcpy(n->item, item);14        n->next = NULL;15    }16    return n;17}18 19void free_list(Node *head) {20    while (head != NULL) {21        Node *next = head->next;22        free(head);23        head = next;24    }25}26 27int main(void) {28    Node *head = new_node("牛奶");29    head->next = new_node("面包");30    head->next->next = new_node("鸡蛋");31    printf("一共 3 样，现在全部释放\n");32    free_list(head);33    return 0;34}

输出

一共 3 样，现在全部释放

点单步，看最前面的框一个接一个变灰、标上「已释放」，head 一路往后挪，直到变成 NULL。

插到前面、插到中间

在最前面加一个最简单：新节点的 next 指向原来的第一个，新节点就成了新的 head。函数把新的 head 返回来，调用的人存回去：

先猜一猜

这段程序显示什么？

1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4 5typedef struct node {6    char item[16];7    struct node *next;8} Node;9 10Node *push_front(Node *head, const char *item) {11    Node *n = malloc(sizeof(Node));12    strcpy(n->item, item);13    n->next = head;14    return n;15}16 17void free_list(Node *head) {18    while (head != NULL) {19        Node *next = head->next;20        free(head);21        head = next;22    }23}24 25int main(void) {26    Node *list = NULL;27    list = push_front(list, "牛奶");28    list = push_front(list, "面包");29    list = push_front(list, "鸡蛋");30    for (Node *p = list; p != NULL; p = p->next) {31        printf("%s ", p->item);32    }33    printf("\n");34    free_list(list);35    return 0;36}

输出

插到中间也只要改两个指针。下面的 insert_after 把新节点接在 prev 后面：

main.c

1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4 5typedef struct node {6    char item[16];7    struct node *next;8} Node;9 10Node *new_node(const char *item) {11    Node *n = malloc(sizeof(Node));12    if (n != NULL) {13        strcpy(n->item, item);14        n->next = NULL;15    }16    return n;17}18 19void insert_after(Node *prev, const char *item) {20    Node *n = new_node(item);21    n->next = prev->next;22    prev->next = n;23}24 25void print_list(Node *head) {26    for (Node *p = head; p != NULL; p = p->next) {27        printf("%s -> ", p->item);28    }29    printf("NULL\n");30}31 32void free_list(Node *head) {33    while (head != NULL) {34        Node *next = head->next;35        free(head);36        head = next;37    }38}39 40int main(void) {41    Node *head = new_node("牛奶");42    head->next = new_node("鸡蛋");43    print_list(head);44    insert_after(head, "面包");45    print_list(head);46    free_list(head);47    return 0;48}

输出

牛奶 -> 鸡蛋 -> NULL
牛奶 -> 面包 -> 鸡蛋 -> NULL

点单步，走进 insert_after 看两步：先让新节点指向「鸡蛋」，再让「牛奶」改指新节点。顺序不能反：要是先改 prev->next，「鸡蛋」的地址就丢了，后半串再也找不回来。

删掉一个

删除也是改指针：让前一个节点跳过它，直接指向它的下一个，再把它 free 掉。要删的正好是第一个时，没有「前一个」，改的是 head：

main.c

1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4 5typedef struct node {6    char item[16];7    struct node *next;8} Node;9 10Node *push_front(Node *head, const char *item) {11    Node *n = malloc(sizeof(Node));12    strcpy(n->item, item);13    n->next = head;14    return n;15}16 17Node *remove_item(Node *head, const char *item) {18    Node *prev = NULL;19    Node *p = head;20    while (p != NULL && strcmp(p->item, item) != 0) {21        prev = p;22        p = p->next;23    }24    if (p == NULL) {25        return head;26    }27    if (prev == NULL) {28        head = p->next;29    } else {30        prev->next = p->next;31    }32    free(p);33    return head;34}35 36void print_list(Node *head) {37    for (Node *p = head; p != NULL; p = p->next) {38        printf("%s -> ", p->item);39    }40    printf("NULL\n");41}42 43int main(void) {44    Node *list = NULL;45    list = push_front(list, "鸡蛋");46    list = push_front(list, "面包");47    list = push_front(list, "牛奶");48    print_list(list);49    list = remove_item(list, "面包");50    print_list(list);51    list = remove_item(list, "牛奶");52    print_list(list);53    list = remove_item(list, "鸡蛋");54    print_list(list);55    return 0;56}

输出

牛奶 -> 面包 -> 鸡蛋 -> NULL
牛奶 -> 鸡蛋 -> NULL
鸡蛋 -> NULL
NULL

while 一边找一边记着前一个节点 prev。没找到（p 走到了 NULL）就什么也不改。点单步，看删「面包」时「牛奶」的箭头怎么绕过它、直接指到「鸡蛋」上，然后「面包」的框变灰，标上「已释放」。最后一样也删掉，list 变回 NULL，空链表显示出来就只有 NULL。

练一练

写好代码，点检查。提示随便看，实在想不出来再看答案。

练习 1

一共多少钱

每个节点是一件商品的价格。走一遍链表，把价格加起来，显示 一共 23.50 元。

要显示

一共 23.50 元

exercise1.c

1#include <stdio.h>2 3typedef struct node {4    double price;5    struct node *next;6} Node;7 8int main(void) {9    Node c = { 4.5, NULL };10    Node b = { 12.0, &c };11    Node a = { 7.0, &b };12    Node *head = &a;13 14    return 0;15}

输出

点「运行」或按 Ctrl+Enter

练习 2

清单上有没有

写函数 contains：清单里有 item 就返回 1，没有就返回 0。程序要显示 面包：1 和 酱油：0。

要显示

面包：1
酱油：0

exercise2.c

1#include <stdio.h>2#include <string.h>3 4typedef struct node {5    char item[16];6    struct node *next;7} Node;8 9int contains(Node *head, const char *item) {10 11}12 13int main(void) {14    Node c = { "鸡蛋", NULL };15    Node b = { "面包", &c };16    Node a = { "牛奶", &b };17    printf("面包：%d\n", contains(&a, "面包"));18    printf("酱油：%d\n", contains(&a, "酱油"));19    return 0;20}

输出

点「运行」或按 Ctrl+Enter

练习 3

加到最后

写函数 push_back，把新节点接在链表最后，返回 head。链表是空的（head 是 NULL）时，新节点就是 head。程序要显示 牛奶 -> 面包 -> 鸡蛋 -> NULL。

要显示

牛奶 -> 面包 -> 鸡蛋 -> NULL

exercise3.c

1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4 5typedef struct node {6    char item[16];7    struct node *next;8} Node;9 10Node *new_node(const char *item) {11    Node *n = malloc(sizeof(Node));12    strcpy(n->item, item);13    n->next = NULL;14    return n;15}16 17Node *push_back(Node *head, const char *item) {18 19}20 21void free_list(Node *head) {22    while (head != NULL) {23        Node *next = head->next;24        free(head);25        head = next;26    }27}28 29int main(void) {30    Node *list = NULL;31    list = push_back(list, "牛奶");32    list = push_back(list, "面包");33    list = push_back(list, "鸡蛋");34    for (Node *p = list; p != NULL; p = p->next) {35        printf("%s -> ", p->item);36    }37    printf("NULL\n");38    free_list(list);39    return 0;40}

输出

点「运行」或按 Ctrl+Enter

这一课学会了

链表由节点组成：每个节点放一个值和一个 next 指针，最后一个的 next 是 NULL；head 指着第一个。
节点结构体里写 struct node *next，因为那时 typedef 的名字还没有。
走一遍链表：for (Node *p = head; p != NULL; p = p->next)。没有下标，只能从头一个一个走；走过头会碰到 NULL。
节点用 malloc 建在堆上；插到前面、插到中间、删掉一个，都只改一两个指针，别的节点不用动。
改指针的顺序要紧：插入时先接上后面的，再改前面的。
释放整个链表：free 之前先存好 next，不然就是用了已经 free 的内存。