单链表定义

动机

在本章中，我们将讨论单链表。有人可能会感到惊讶：为什么在一门关于指针和内存管理的课程中要讨论数据结构？
答案是：我们并不关心数据结构本身。我们关注的是从零开始实现它，因为这有助于练习指针操作和动态内存分配。

链表相关的函数在概念上很简单，但通常需要借助内存示意图，并仔细关注如何正确地操作指针。
虽然我们通常不需要编写大量代码，但这些代码在指针处理方面具有挑战性。

链表简介

存在多种类型的列表，例如单向链表、双向链表、循环链表、通用链表等。在本章中，我们将讨论单向链表。
链表中的元素称为节点。每个节点包含该元素的值以及指向列表中下一个元素的指针。

直观地，我们可以将链表看作如下图所示。例如，每个节点存储一个值（1、2、3、4 或 5），每个节点指向下一个节点，最后一个节点则不指向任何地方（因为它已是最后一个节点）。

类型定义

我们可以使用结构体来定义链表的节点，假设这是一个整数链表：

1typedef struct SList
2{
3    int value;
4    struct SList* next;
5} TList;

注意，我们必须为结构体命名。next 字段是一个指向列表中下一个节点的指针，因此这种结构具有递归性质——一个节点包含对另一个节点的指针。
typedef 定义的 TList 在结构体内部不可见，因此我们必须使用结构体名称 struct SList。

我们可以重新绘制链表，使两个字段更加清晰。

最后一个节点在图中指向 NULL。我们添加这一部分是为了更清楚地表达，但在后续内容中将省略。我们不再为最后一个节点之后绘制连接箭头。
在课程文本中，我们将链表表示为 [1, 2, 3, 4, 5]。

我们称这种链表为单向链表，因为从图中可以看出，每个节点仅维护一个指向下一个节点的链接（next）。
相比之下，在双向链表中，每个节点维护两个指针：一个指向下一个元素，另一个指向前一个元素。

第一段代码

让我们尝试编写一些代码，创建如上图所示的 [1, 2, 3, 4, 5] 链表。

我们首先编写一个辅助函数 allocNode（第10行）。它接收一个值作为参数，并动态分配一个节点。函数将节点的值设置为传入的参数，并将 next 字段设为 NULL。
将 next 设为 NULL 实际上就创建了一个仅包含一个节点的链表。

然后我们可以使用 allocNode 创建五个节点，每个节点对应值 1 到 5。在获得这些节点后，我们可以设置 node1->next = node2，node2->next = node3，依此类推（第64-67行）。

该函数较长，因为我们必须在每次节点分配后检查是否失败，并在失败时释放之前已分配的节点。注意，这里必须这样做，因为我们希望逐步构建链表，以使过程清晰可见。我们也可以使用 for 循环来避免重复代码。

函数返回链表第一个节点的指针。这个指针就是我们操作链表所需的全部信息（第69行）。

链表中的第一个节点被称为链表的头节点或链表头。

1#include <stdio.h>
2#include <stdlib.h>
3
4typedef struct SList
5{
6    int value;
7    struct SList* next;
8} TList;
9
10TList* allocNode(int value)
11{
12    TList* node = malloc(sizeof(TList));
13    if (node == NULL) {
14        return NULL;
15    }
16
17    node->value = value;
18    node->next = NULL;
19
20    return node;
21}
22
23TList* createExampleList()
24{
25    TList* node1 = allocNode(1);
26    if (node1 == NULL) {
27        return NULL;
28    }
29
30    TList* node2 = allocNode(2);
31    if (node2 == NULL) {
32        free(node1);
33        return NULL;
34    }
35
36    TList* node3 = allocNode(3);
37    if (node3 == NULL) {
38        free(node1);
39        free(node2);
40        return NULL;
41    }
42
43    TList* node4 = allocNode(4);
44    if (node4 == NULL) {
45        free(node1);
46        free(node2);
47        free(node3);
48        return NULL;
49    }
50
51    TList* node5 = allocNode(5);
52    if (node5 == NULL) {
53        free(node1);
54        free(node2);
55        free(node3);
56        free(node4);
57        return NULL;
58    }
59
60    node1->next = node2;
61    node2->next = node3;
62    node3->next = node4;
63    node4->next = node5;
64
65    return node1;
66}
67
68int main()
69{
70    TList* exampleList = createExampleList();
71    return 0;
72}

代码可以正常编译，但由于没有编写打印函数，我们无法显示链表内容。因此，让我们来实现一个。

要编写打印函数，我们可以从 createExampleList 返回的头节点开始遍历，依次访问下一个节点，直到遇到 NULL。当 next 为 NULL 时，说明已到达链表末尾。

查看下方代码的第4行。printList 函数接收一个指针，即链表的头节点。
如果链表为 NULL，说明链表为空，我们应打印相应提示。

接着我们复制这个指针，以防止丢失原始指针。这一步在当前代码中可选，但是一种良好实践。在遍历链表时，我们会不断用下一个节点的指针覆盖当前指针。通过引入另一个变量 current，我们可以确保 list 仍指向链表的第一个节点，这样如果我们需要在 printList 函数中再次遍历链表，就会很方便。

第15行的 while 循环会在 current 不为 NULL 时持续执行代码，换句话说，只要未到达链表末尾就继续执行。

然后我们使用 current->value 打印节点值，并通过 current = current->next 移动到下一个节点。

假设我们在第一次迭代中，current 指向链表的第一个节点（值为 1）。我们打印 1，然后将 current 更新为 current->next（即值为 2 的节点）。重复此过程，直到 current 变为 NULL，表示链表结束。

注意：我们隐藏了之前的代码。目前只显示新添加的函数。

1#include <stdio.h>
2#include <stdlib.h>
3
4void printList(TList* list)
5{
6    if (list == NULL) {
7        printf("List: empty");
8        return;
9    }
10
11    printf("List: ");
12
13    TList* current = list;
14    while (current != NULL) {
15        printf("%d ", current->value);
16        current = current->next;
17    }
18
19    printf("\n");
20    return;
21}
22
23int main()
24{
25    TList* exampleList = createExampleList();
26    printList(exampleList);
27
28    return 0;
29}

如我们所见，输出结果正确。不过，让我们详细走一遍执行过程，以确保理解指针操作。

如果 current = current->next 这种写法仍显得奇怪，我们可以将其改写为更直观的形式：

1TList* nextNode = current->next;
2current = nextNode;

释放内存

我们仍然需要释放内存。让我们编写一个 freeList 函数来释放链表内存。

在 freeList 中：

• 我们以与打印链表相同的方式遍历链表。
• 对当前节点调用 free 来释放其内存（第10行）。

1#include <stdio.h>
2#include <stdlib.h>
3
4void freeList(TList* list)
5{
6    TList* current = list;
7    while (current != NULL) {
8        TList* next = current->next;
9        free(current);
10        current = next;
11    }
12}
13
14int main()
15{
16    TList* exampleList = createExampleList();
17    printList(exampleList);
18
19    freeList(exampleList);
20
21    return 0;
22}

这里有一个细节需要注意：我们必须采用第二种方式推进遍历，并在调用 free 之前保存下一个节点的指针。否则会丢失该指针。

假设以下顺序：

1free(current);
2current = current->next;

在 free 之后，current 已不再有效，因此 current->next 也无效。这相当于试图解引用一个悬空指针。

结语

在今后所有关于链表的编程练习中，你可以假设有以下函数可用：

• allocNode：用于分配节点
• createExampleList：用于构建一个示例链表
• printList：用于打印链表
• freeList：用于释放链表内存

同时，你也可以假定链表结构定义始终存在。