2.8 链表：关系存哪里，用C怎么表示

2.8.1 放弃"相邻"约定，关系存哪里

顺序存储和链式存储回答的是同一个问题：线性表的元素和它们之间的一对一关系，怎么放进一维的内存。顺序表的答案是"相邻格子放相邻元素"，关系隐含在位置里，不占空间，按位置取元素一步到位；但2.6节看到了它的代价：中间插入必须挪动后面的所有元素。那么，放弃这条约定会怎样？

放弃之后，元素可以散落在内存的任何地方，插入一个新元素时随便找个空格子放进去就行，不用挪动任何人。但马上出现新问题：关系没了。顺序表里"a在c后面"这条关系是靠"a就放在c的下一格"表示的，现在两个字符各在一处，谁也不挨着谁，怎么知道a在c后面？

第1章已经给过答案：关系不能隐含在位置里，就明确地存下来——在每个元素旁边记下"下一个元素在哪"，也就是下一个元素的地址。第1章用整数看过这个做法，这里换成字符再看一遍，因为后面要用它实现编辑器。

假设一行只有三个字符cat，我们不再把它们挨着放，而是分开存在内存的一段格子里：c在100号，t在104号，a在108号。

┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ c │   │   │   │ t │   │   │   │ a │   │   │   │   │   │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115

c确实在第一格，可是接下来按位置往后找，找到的是t，不是a。a跑到了t的后面。也就是说，位置已经不能告诉我们谁在谁后面了。要读出cat，得有别的办法知道：c的下一个是a，a的下一个是t。这些关系存在哪？

办法是把它们明确地记下来：在每个字符右边的格子里，写上下一个字符的地址。

┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ c │108│   │   │ t │ 0 │   │   │ a │104│   │   │   │   │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115

现在从c出发能走通了：101号格子记着108，去108号找到a；109号记着104，去104号找到t；105号记着0，表示走到头了。（地址0是特殊值，任何变量都不会住在0号格子，所以用它表示"没有下一个"。）走的路线是100→108→104，在内存里先往后跳、再往回跳，但读出来正好是cat。逻辑顺序不靠位置表示，靠的是这些右格里的数字。

要特别提醒一句：右格里的108、104不是数据，它们是另一个格子的编号。同样是格子里的内容，左格存的是字符，右格存的是地址。

现在每个元素占的不再是一个格子，而是两个：一个存数据，一个存下一个元素的地址。这两个格子合起来叫一个结点。一个个结点用地址串起来，就是链表。

按内存位置画图看得清"分开存"，但看不清"顺序"。把三个结点按逻辑顺序重新摆一遍，右格里的地址用箭头画出来，方框下面标出它在内存里的位置：

head = 100
  │
  ▼
┌───┬─────┐     ┌───┬─────┐     ┌───┬─────┐
│ c │ 108 │────►│ a │ 104 │────►│ t │  0  │
└───┴─────┘     └───┴─────┘     └───┴─────┘
    100             108             104

这张图和上一张是同一份数据的两种画法：上一张按内存位置排，这一张按逻辑顺序排。方框下面的数字是它在上一张图里的位置，右格里的数字就是箭头指向的那个方框的地址。head是我们另外记下的第一个结点的地址，有了它才知道从哪里开始走。

后面讲操作时，图一律用这种箭头画法，并且大多数时候不再标地址数字——代码里我们永远看不到100、108这些数，地址存在指针变量里，指针变量替我们记着，箭头就是指针。只有在讲插入和删除、需要看清"右格里的数字怎么变"的时候，才把数字标回来。

2.8.2 用C表示结点和链表

结点

一个结点有两部分：一个字符，一个指向下一个结点的地址。用结构体表示：

typedef struct Node {
    char         data;    /* 数据 */
    struct Node *next;    /* 下一个结点的地址 */
} Node;

这里有一处第一次见到的写法：结构体里面有一个指向自己这种结构体的指针。next存的是"下一个结点的地址"，下一个结点也是一个Node，所以next的类型是"指向Node的指针"。

注意结构体的名字写了两遍：开头的struct Node和结尾typedef出来的Node。这是因为在定义next的那一行，typedef还没有完成，Node这个简写还不存在，只能用完整的struct Node *。定义结束之后，其他地方就都可以用Node了。

结点从哪来

顺序表的格子是Init时一次申请一整段。链表的结点是零散的，谁需要谁申请：每插入一个元素，就向系统要一个结点大小的空间，把字符放进去。2.7节用过的malloc正好干这个事。写成一个小函数：

Node *NewNode(char x) {
    Node *p = (Node *)malloc(sizeof(Node));
    if (p == NULL) return NULL;
    p->data = x;
    p->next = NULL;
    return p;
}

malloc(sizeof(Node))申请一个结点的空间，返回它的地址；把字符填进data，next先置为NULL——这就是上一节说的地址0，C语言里写作NULL，表示"暂时不指向任何结点"。函数返回这个新结点的地址。

对应到上一节的图：NewNode('c')就是造出了c那个方框，它的右格暂时是0。

整个表用什么代表

有了结点，还要有一个东西代表"整张表"。只要记住第一个结点的地址，就能顺着next走完全表，所以最少只需要一个指针head。但2.2节定义的Length要返回长度，如果每次都从头数一遍，Length就成了O(n)；顺序表的Length是O(1)，链表没理由做得更差。所以再加一个计数器，和顺序表的结构对称：

typedef struct {
    Node *head;     /* 第一个结点的地址 */
    int   length;   /* 结点个数 */
} LinkList;

空表就是head为NULL、length为0。上一节cat那张图，就是一个head指向c结点、length为3的LinkList。

从现在起，六个操作的参数是LinkList *L，和顺序表的SeqList *L签名完全一样，只是类型名不同。2.5节的编辑器main里，把SeqList改成LinkList，其余能不能一行不改地跑起来，是2.10节要验证的事。

先手工搭一个

在写六个操作之前，先不借助任何操作，手工把cat搭出来、再走一遍，把结点、指针、箭头和代码对上：

LinkList L;
L.head = NewNode('c');                 /* 造 c，head 指向它 */
L.head->next = NewNode('a');           /* 造 a，c 的 next 指向它 */
L.head->next->next = NewNode('t');     /* 造 t，a 的 next 指向它 */
L.length = 3;

for (Node *p = L.head; p != NULL; p = p->next)
    putchar(p->data);                  /* 输出 cat */

L.head->next是"head指向的结点的next"，也就是a的地址；L.head->next->next是a的next，也就是t的地址。一连串箭头就是顺着链一站一站往下走。

最后那个for循环是链表最基本的动作，后面反复出现：p从第一个结点开始，每次p = p->next跳到下一个，直到p变成NULL说明走到头了。上一节按地址100→108→104读一遍，就是这个循环。

当然，L.head->next->next这种写法只能演示，不能用来干活——插第100个字符要写100个箭头。怎么在任意位置插入、删除、取元素，就是下一节六个操作要解决的问题。