图7-1 使用List-list建立一个三节点的链表
链表是零或多个指针的序列。包含零个指针的链表是空链表。链表中指针的数目是其长度。几乎每个非平凡的应用程序都会以某种形式使用链表。在程序中链表是如此普遍，以至于有些语言将链表作为内建类型，LISP、Scheme和ML是最著名的例子。
链表很容易实现，因此程序员通常对手头的每个应用程序都重新实现链表，另外，虽然大多数特定于应用程序的链表接口有很多相似性，但链表没有广为接受的标准接口。如下所述的List抽象数据类型提供了大多数特定于应用程序的链表接口中的许多功能。第11章描述的序列，是表示链表的另一种方法。
完整的List接口如下：
〈list.h
〉≡
#ifndef LIST_INCLUDED
#define LIST_INCLUDED
#define T List_T
typedef struct T *T;
struct T {
T rest;
void *first;
};
extern T List_append (T list, T tail);
extern T List_copy (T list);
extern T List_list (void *x, ...);
extern T List_pop (T list, void **x);
extern T List_push (T list, void *x);
extern T List_reverse(T list);
extern int List_length (T list);
extern void List_free (T *list);
extern void List_map (T list,
void apply(void **x, void *cl), void *cl);
extern void **List_toArray(T list, void *end);
#undef T
#endif
一个List_T是一个指向某个struct List_T实例的指针。大部分ADT都隐藏其类型的表示细节。链表展现了这些细节，是因为对于这种特定的ADT来说，隐藏细节带来的复杂性超出了好处。
List_T有一种平凡的表示，从接口可以看到，这种表示采用的链表元素是包含两个字段的结构，我们很难想象到，居然有许多其他种表示能够在隐藏该事实的情况下带来足够多的好处。章末的习题探讨了其中一些方案。
披露List_T的表示从几个方面简化了接口及其使用。例如，struct List_T类型的变量可以静态地定义并初始化，这对于在编译时构建链表很有用，且避免了内存分配。类似地，其他结构可以将struct List_T实例嵌入到自身之中。值为NULL的List_T是空链表，这是一种很自然的表示，而且访问first和rest字段不需要函数。
该接口中的所有例程对任何链表参数都可以接受NULL值的T，并将其解释为空链表。
List_list创建并返回一个链表。调用该函数时，需要传递N+1个指针作为参数，前N个指针为非NULL，最后一个为NULL指针；该函数会创建一个包含N个结点的链表，各个结点的first字段包含了N个非NULL的指针，而第N个结点的rest字段为NULL。例如，下列赋值操作
List_T p1, p2;
p1 = List_list(NULL);
p2 = List_list("Atom", "Mem", "Arena", "List", NULL);
分别返回空链表和一个包含4个结点的链表（其中的first字段分别指向字符串"Atom"、"Mem"、"Arena"、"List"）。List_list可能引发Mem_Failed异常。
List_list假定其参数列表的可变部分传递的指针是void。函数的原型中没有提供隐式转换所需的必要信息，因而对于用作第二个及后续参数的指针来说，程序员必须对char和void以外的指针提供显式转换。例如，为构建一个包含四个子链表的链表，四个子链表都只有一个链表元素，分别包含了字符串"Atom"、"Mem"、"Arena"、"List"，正确的调用如下：
p = List_list(List_list("Atom", NULL),
(void *)List_list("Mem", NULL),
(void *)List_list("Arena", NULL),
(void *)List_list("List", NULL), NULL);
忽略例子中给出的强制转换是一个未检查的运行时错误。这种转换是可变长度参数列表的缺陷之一。
List_push(T list, void*x)在链表list的起始处添加一个包含x的新结点，并返回新的链表。List_push可能引发Mem_Failed异常。List_push是创建新链表的另一种方法，例如，
p2 = List_push(NULL, "List"); p2 = List_push(p2, "Arena"); p2 = List_push(p2, "Mem"); p2 = List_push(p2, "Atom");
上述代码与前文中对p2的赋值操作，所创建的链表是相同的。
给定一个非空的链表，List_pop(T list, void**x)将第一个结点的first字段赋值给*x（如果x不是NULL指针），移除第一个结点并释放其内存，最后返回结果链表。给定一个空链表，List_pop只是返回原链表，并不修改*x。
List_append(T list, T tail)将一个链表附加到另一个：该函数将tail赋值给list中最后一个结点的rest字段。如果list为NULL，该函数返回tail。这样，下面的代码
p2=List_append(p2, List_list("Except", NULL));
首先将包含字符串"Except"的单元素链表附加到前面创建的包含四个元素的链表，而后将p2设置为指向新的包含5个元素的链表。
List_reverse首先逆转其参数链表中结点的顺序，而后返回结果链表。例如，
p2 = List_reverse(p2);
返回的链表包含5个元素，依次是"Except"、"List"、"Arena"、"Mem"、"Atom"。
到目前为止描述的大部分例程都是破坏性的 （或非应用性的 ，non-applicative），它们可能改变传递进来的链表，并返回结果链表。List_copy是一个应用性的 （applicative）函数：它复制其参数链表，并返回副本。因而，在执行下述代码之后
List_T p3 = List_reverse(List_copy(p2));
p3链表包含"Atom"、"Mem"、"Arena"、"List"、"Except"，p2保持不变。List_copy可能引发Mem_Failed异常。
List_length返回其参数链表中的结点数目。
List_free的参数为一个指向T的指针。如果*list不是NULL，List_free将释放*list链表中的所有结点并将其设置为NULL指针。如果*list为NULL，List_free则没有效果。将NULL指针传递给List_free是一个已检查的运行时错误。
List_map对list链表中的每个结点调用apply指向的函数。客户程序可以向List_map传递一个特定于应用程序的指针cl，该指针接下来传递给*apply，用作第二个参数。对链表中的每个结点，都会用指向结点first字段的指针和cl作为参数来调用*apply。因为调用*apply时使用的是指向first字段的指针，因此first字段可能会被apply修改。apply和cl合称闭包 （closure）或回调 （callback）：它们规定了一个操作和一些用于该操作的上下文相关数据。例如，给定下述函数：
void mkatom(void **x, void *cl) {
char **str = (char **)x;
FILE *fp = cl;
*str = Atom_string(*str);
fprintf(fp, "%s\n", *str);
}
那么调用List_map(p3, mkatom, stderr)会将p3链表中的字符串用相等的原子替换，并输出下列内容：
Atom Mem Arena List Except
到标准错误输出。另一个例子是
void applyFree(void **ptr, void *cl) {
FREE(*ptr);
}
在释放链表本身之前，可以用该函数释放各个结点的first字段所指向的内存空间。例如：
List_T names; ... List_map(names, applyFree, NULL); List_free(&names);
上述代码将释放链表names中的数据，然后释放链表中的各个结点本身。如果apply改变链表，那么这是一个未检查的运行时错误。
给定一个包含N个值的链表，List_toArray(T list, void * end)将创建一个数组，数组中的元素0到元素N-1分别包含了链表中N个结点的first字段值，数组中的元素N包含end的值，end通常是一个NULL指针。List_toArray返回一个指向数组第一个元素的指针。例如，下述代码可以按排序后的次序输出p3中的各个元素：
int i;
char **array = (char **)List_toArray(p3, NULL);
qsort((void **)array, List_length(p3), sizeof (*array),
(int (*)(const void *, const void *))compare);
for (i = 0; array[i]; i++)
printf("%s\n", array[i]);
FREE(array);
按这个例子所暗示的，客户程序必须释放List_toArray返回的数组。如果链表为空，List_toArray返回一个单元素数组。List_toArray可能引发Mem_Failed异常。compare及其与标准库函数qsort的协同使用，将在8.2节描述。
〈list.c 〉≡ #include <stdarg.h> #include <stddef.h> #include "assert.h" #include "mem.h" #include "list.h" #define T List_T 〈functions 79〉
List_push是最简单的链表函数。它分配一个结点，初始化该结点，并返回指向该结点的指针：
〈functions
79〉≡
T List_push(T list, void *x) {
T p;
NEW(p);
p->first = x;
p->rest = list;
return p;
}
另一个创建链表的函数List_list则更为复杂，因为它必须处理数量可变的参数，而且对参数列表中每一个不是NULL的指针参数，都必须向链表附加一个新的结点。为此，该函数用一个双重指针，来指向表示应该分配的新结点的指针：
〈functions
79〉+≡
T List_list(void *x, ...) {
va_list ap;
T list, *p = &list;
va_start(ap, x);
for ( ; x; x = va_arg(ap, void *)) {
NEW(*p);
(*p)->first = x;
p = &(*p)->rest;
}
*p = NULL;
va_end(ap);
return list;
}
p最初指向list，因此循环体中的操作会把指向第一个结点的指针赋值给list。此后，p指向链表中最后一个结点的rest字段，因此对*p的赋值就是向链表添加了一个结点。图7-1演示了使用List_list建立一个三结点的链表时，对p的初始化以及for循环体中的语句的效果。
图7-1 使用List-list建立一个三节点的链表
每一次循环都将可变参数列表中的下一个指针参数赋值给x，当遇到第一个NULL指针参数时退出循环，当然x的初始值也可能是NULL。这种惯用法确保了List_list(NULL)返回空链表，即NULL指针。
List_list对双重指针（即List_T*）的使用，在许多链表处理算法中是很有代表性的。它使用一种简明的机制处理了两种情况：向可能为空的链表添加初始结点，向非空的链表添加内部结点。List_append示范了对该惯用法的另一种使用：
〈functions
79〉+≡
T List_append(T list, T tail) {
T *p = &list;
while (*p)
p = &(*p)->rest;
*p = tail;
return list;
}
List_append用p来遍历list，p最终指向链表末尾结点的rest字段（为NULL指针），List_append应该将tail赋值给该字段。如果list本身是NULL指针，循环结束时p指向list，同样可以达到将tail附加到空链表的预期效果。
List_copy是List接口中最后一个使用双重指针惯用法的函数：
〈functions
79〉+≡
T List_copy(T list) {
T head, *p = &head;
for ( ; list; list = list->rest) {
NEW(*p);
(*p)->first = list->first;
p = &(*p)->rest;
}
*p = NULL;
return head;
}
双重指针无法简化List_pop或List_reverse，因此对这两个函数来说，更显然的实现方法就足够了。List_pop删除一个非空链表中的第一个结点并返回新链表，或返回空链表：
〈functions
79〉+≡
T List_pop(T list, void **x) {
if (list) {
T head = list->rest;
if (x)
*x = list->first;
FREE(list);
return head;
} else
return list;
}
如果x不为NULL，那么在释放第一个结点之前，将其first字段赋值给*x。请注意，List_pop在释放list指向的结点之前，必须保存list->rest字段。
List_reverse用两个指针list和next来遍历链表一次，并使用这两个指针将链表就地反转，head总是指向反转后链表的第一个结点：
〈functions
79〉+≡
T List_reverse(T list) {
T head = NULL, next;
for ( ; list; list = next) {
next = list->rest;
list->rest = head;
head = list;
}
return head;
}
图7-2说明了处理链表第三个元素时，刚好执行完循环体中第一个语句（对next的赋值）的情形。
图7-2 处理链表中第三个元素的情形
此时，next指向list的后继结点，如果list指向链表中最后一个结点，则next为NULL， head指向当前的逆向链表，该链表从list的前趋结点开始，如果list指向链表的第一个结点，则head为NULL。循环体中的第二和第三条语句，将list指向的结点推入到head链表的头部，循环的递增表达式list=next将list推进到当前结点的后继结点，此时，链表的情形如图7-3所示。
图7-3 将list推进到当前结点的后继结点的链表
在接下来执行循环体的过程中，next将会再次推进。
List_length遍历list统计结点数目，List_free遍历list以释放每一个结点：
〈functions
79〉+≡
int List_length(T list) {
int n;
for (n = 0; list; list = list->rest)
n++;
return n;
}
void List_free(T *list) {
T next;
assert(list);
for ( ; *list; *list = next) {
next = (*list)->rest;
FREE(*list);
}
}
List_map看起来很复杂，但其实是平凡的，因为闭包函数完成了所有工作。List_map只需遍历list，用指向链表中每一个结点的first字段的指针和客户程序相关的指针cl，来调用闭包函数即可：
〈functions
79〉+≡
void List_map(T list,
void apply(void **x, void *cl), void *cl) {
assert(apply);
for ( ; list; list = list->rest)
apply(&list->first, cl);
}
List_toArray分配一个N+1个元素的数组，用以容纳一个N元素链表中的指针，并将链表中的指针复制到数组中。
〈functions
79〉+≡
void **List_toArray(T list, void *end) {
int i, n = List_length(list);
void **array = ALLOC((n + 1)*sizeof (*array));
for (i = 0; i < n; i++) {
array[i] = list->first;
list = list->rest;
}
array[i] = end;
return array;
}
对空链表分配一个单元素数组看起来是有点浪费，但这样做意味着List_toArray总是返回一个指向数组的非NULL指针，因此客户程序从不需要检查NULL指针。
[Knuth，1973a]描述了操作单链表的所有重要算法（如List接口提供的那些），以及操作双链表的算法（本书中由Ring接口提供，在第12章描述）。
在表处理语言如LISP和Scheme中，以及函数式语言如ML [Ullman，1994]中，一切东西都是链表。[Abelson and Sussman，1985]说明了如何使用链表来解决几乎任何问题，而该书只是许多此类教科书之一，该书使用了Scheme。
7.1 设计一个链表ADT，隐藏链表的表示，且不使用NULL指针来表示空链表。首先设计接口，然后完成实现。一种方法是将List_T作为指向表头的不透明指针，表头中包含一个指针指向链表本身，或两个指针，分别指向链表的第一个和最后一个结点。表头还可以保存链表的长度。
7.2 重写List_list、List_append和List_copy，不使用双重指针。
7.3 使用双重指针重写List_reverse。
7.4 List_append在许多应用程序中是最常用的链表操作之一，它必须遍历到链表的末尾，对一个N元素链表需要花费O(N)时间。循环链表是单链表的另一种表示。Mem接口的稽核实现中的空闲链表，就是循环链表的一个例子。在循环链表中，最后一个结点的rest字段指向第一个结点，链表本身由指向最后一个结点的指针表示。因而，第一个和最后一个结点都可以在常数时间内访问，向循环链表附加另一个链表的操作，也可以在常数时间内完成。为使用循环链表的链表ADT设计一个接口。对于隐藏链表表示和披露链表表示的两种接口，都要进行试验。