外观
2.9 链表的六个操作与头结点
2.9.1 初始化、求长度、取第i个元素、查找
初始化和求长度
空表是head为NULL、length为0：
c
void Init(LinkList *L) {
L->head = NULL;
L->length = 0;
}
int Length(LinkList *L) {
return L->length;
}取第i个元素
顺序表的Get是一次下标运算。链表没有下标，第i个结点在哪只有一个办法知道：从head出发，顺着next走i步。
以cat为例，Get(L, 2)要取t。从head出发，走0步是c，走1步到a，走2步到t：
text
head
│
▼
┌───┬───┐ ┌───┬───┐ ┌───┬───┐
│ c │ ●─┼────►│ a │ ●─┼────►│ t │ ╱ │
└───┴───┘ └───┴───┘ └───┴───┘
p 第0步 p 第1步 p 第2步用一个指针p记当前走到哪，每走一步p = p->next，走够i步停下，p->data就是要的元素：
c
char Get(LinkList *L, int i) {
if (i < 0 || i >= L->length) return '\0';
Node *p = L->head;
for (int k = 0; k < i; k++)
p = p->next;
return p->data;
}把Get(L, 2)带进去走一遍：p先等于head，指向c；k=0时p = p->next，指向a；k=1时再走一步，指向t；k=2不满足k<2，循环结束，返回p->data即t。
"从head出发走到第i个结点"这个动作，后面的Insert和Delete也要用，单独抽成一个函数：
c
Node *NodeAt(LinkList *L, int i) { /* 返回第i个结点的地址 */
Node *p = L->head;
for (int k = 0; k < i; k++)
p = p->next;
return p;
}Get就变成一行：return NodeAt(L, i)->data;。
查找
Locate也是从head走到尾，只是每到一个结点比较一下数据，同时用一个计数器记走到了第几个：
c
int Locate(LinkList *L, char x) {
int i = 0;
for (Node *p = L->head; p != NULL; p = p->next, i++)
if (p->data == x) return i;
return -1;
}Locate(L, 't')：p在c，不等，i变1；p在a，不等，i变2；p在t，相等，返回2。
2.9.2 在第i个位置插入：三种位置
这是链表最重要的操作，也是它相对顺序表的优势所在：不挪动任何结点，新结点随便放在哪个空格子里，只改地址。插入位置不同，要改的地址不同，分三种情况看。
插在第0个位置。 比如在cat最前面插入b。新结点b要成为第一个，那么b的next应该指向原来的第一个结点c，而head应该改为指向b。要改的两个地址是b的next和head：
text
head ──────────────┐
▼
┌───┬───┐ ┌───┬───┐ ┌───┬───┐ ┌───┬───┐
│ b │ ●─┼────►│ c │ ●─┼────►│ a │ ●─┼────►│ t │ ╱ │
└───┴───┘ └───┴───┘ └───┴───┘ └───┴───┘
▲
└── head 改为指向这里空表也是这种情况：head是NULL，b的next得到NULL，正好是末尾标记；head改为指向b。不需要额外处理。
插在中间。 比如在a和t之间插入x，即Insert(L, 2, 'x')，结果应为caxt。要改的是x的next和a的next，head不动。但这里有一个顺序表没有的麻烦：我们手里只有head，a在哪并不知道。所以第一步不是改地址，而是找到a——从head出发走一步，这正是NodeAt(L, 1)。找到之后才能改。下面几张图把地址标出来，看清右格里的数字怎么变。假设x放在102号。
第一步，从head走到第1个结点a，用prev记住它：
text
head = 100
│
▼
┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐
│ c │ 108 │────►│ a │ 104 │────►│ t │ 0 │
└───┴─────┘ └───┴─────┘ └───┴─────┘
100 108 104
prev第二步，造出x结点，此时它的next还是0，谁也不指向它：
text
┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐
│ c │ 108 │────►│ a │ 104 │────►│ t │ 0 │
└───┴─────┘ └───┴─────┘ └───┴─────┘
100 108 104
prev
┌───┬─────┐
│ x │ 0 │
└───┴─────┘
102第三步，让x的next指向t。t的地址是104，它现在记在prev的右格里，把它抄到x的右格：
text
┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐
│ c │ 108 │────►│ a │ 104 │────►│ t │ 0 │
└───┴─────┘ └───┴─────┘ └───┴─────┘
100 108 ▲ 104
prev │
┌───┬──┴──┐
│ x │ 104 │
└───┴─────┘
102第四步，让prev的next指向x。把a的右格从104改成102：
text
┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐
│ c │ 108 │────►│ a │ 102 │ │ t │ 0 │
└───┴─────┘ └───┴───┬─┘ └───┴─────┘
100 108 │ ▲ 104
prev │ │
│ ┌───┬──┴──┐
└►│ x │ 104 │
└───┴─────┘
102从head出发：100→108→102→104，读出caxt。c、t两个结点一个没动，只改了两个右格。
第三步和第四步的顺序不能反。如果先做第四步，把a的右格改成102，那么t的地址104就没人记着了——它原本只存在a的右格里。这时再做第三步，想让x指向t，已经不知道t在哪。先让新结点指向后一个，再让前一个指向新结点，这是链表插入必须记住的顺序。
注意四步里只有后两步是真正的插入，第一步"找到前一个结点"是走出来的，位置越靠后走得越远。这一点2.11节比较效率时会再说。
插在末尾。 比如在t后面插入s，即Insert(L, 3, 's')，得到cats。找到第2个结点t，让s的next指向t的next（是NULL），再让t的next指向s。和中间插入是同一套动作，只是"后一个"恰好是NULL，不需要单独处理。
所以三种情况其实是两种：第0个位置改head，其余位置找到第i−1个结点prev、改prev的next。写成代码：
c
int Insert(LinkList *L, int i, char x) {
if (i < 0 || i > L->length) return 0;
Node *q = NewNode(x);
if (q == NULL) return 0;
if (i == 0) { /* 插在最前面：没有前一个结点 */
q->next = L->head;
L->head = q;
} else {
Node *prev = NodeAt(L, i - 1); /* 先找到前一个结点 */
q->next = prev->next; /* 先：新结点指向后一个 */
prev->next = q; /* 后：前一个指向新结点 */
}
L->length++;
return 1;
}2.9.3 用main从空表跑一遍
2.8.2节的cat是手工用->next->next搭的，现在用Insert从空表把它造出来，再插一个x，看结果是否和上面的图一致：
c
int main(void) {
LinkList L;
Init(&L);
const char *s = "cat";
for (int i = 0; s[i]; i++) Insert(&L, i, s[i]); /* 逐个追加 */
Insert(&L, 2, 'x');
for (Node *p = L.head; p != NULL; p = p->next)
putchar(p->data); /* 输出 caxt */
putchar('\n');
return 0;
}为了能和图对上，假设NewNode依次拿到的地址是100、108、104，x拿到102。逐次跟踪。
第一次，Insert(&L, 0, 'c')。表是空的，head为NULL。q是新结点c，在100号。i等于0，走第一个分支：q->next = L->head，c的next得到NULL；L->head = q，head变成100。长度变1。
text
改之前 改之后
head = NULL head = 100
│
┌───┬─────┐ ▼
│ c │ 0 │ ┌───┬─────┐
└───┴─────┘ │ c │ 0 │
100 └───┴─────┘
100第二次，Insert(&L, 1, 'a')。q是a，在108号。i不为0，走第二个分支：prev = NodeAt(L, 0)，从head走0步，得到c；q->next = prev->next，c的next是NULL，a的next得到NULL；prev->next = q，c的next变成108。长度变2。这是"插在末尾"的情况：
text
head = 100
│
▼
┌───┬─────┐ ┌───┬─────┐
│ c │ 108 │────►│ a │ 0 │
└───┴─────┘ └───┴─────┘
100 108
prev第三次插t同理，也是追加，prev是a，t在104号。三次之后表是cat，head=100，三个结点的next依次是108、104、0，和2.8.1节的图完全一样。
第四次，Insert(&L, 2, 'x')。q是x，在102号。prev = NodeAt(L, 1)，走一步得到a；q->next = prev->next，把a的next（104）抄给x；prev->next = q，a的next变成102。长度变4。这就是上面"插在中间"的四步，插完的样子：
text
head = 100
│
▼
┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐
│ c │ 108 │────►│ a │ 102 │────►│ x │ 104 │────►│ t │ 0 │
└───┴─────┘ └───┴─────┘ └───┴─────┘ └───┴─────┘
100 108 102 104程序输出caxt。
2.9.4 头结点
Insert的代码里有一个if分支：插在最前面时改的是head，其余位置改的是某个结点的next。Delete也会碰到同样的事：删第0个要改head，删其他的改前一个结点的next。两个操作各多一个分支，不算大问题，但有个技巧能把分支去掉。
办法是在链表最前面固定放一个不存数据的结点，叫头结点。head永远指向头结点，真正的第0个元素是头结点的next：
text
head
│
▼
┌───┬───┐ ┌───┬───┐ ┌───┬───┐ ┌───┬───┐
│ │ ●─┼────►│ c │ ●─┼────►│ a │ ●─┼────►│ t │ ╱ │
└───┴───┘ └───┴───┘ └───┴───┘ └───┴───┘
头结点 第0个 第1个 第2个这样一来，第0个元素前面也有一个结点了。在任何位置i插入，都是"找到第i−1个结点，改它的next"，i=0时第−1个就是头结点，不再特殊。空表也不再是head为NULL，而是head指向一个next为NULL的头结点。
加头结点后，三个函数要调整。Init要造出头结点；NodeAt从头结点出发，走0步得到的是头结点，也就是"第−1个"，走i+1步到第i个；Insert的if分支消失：
c
int Init(LinkList *L) {
L->head = NewNode('\0'); /* 头结点，数据无意义 */
if (L->head == NULL) return 0;
L->length = 0;
return 1;
}
Node *NodeAt(LinkList *L, int i) { /* i=-1 时返回头结点 */
Node *p = L->head;
for (int k = -1; k < i; k++)
p = p->next;
return p;
}
int Insert(LinkList *L, int i, char x) {
if (i < 0 || i > L->length) return 0;
Node *q = NewNode(x);
if (q == NULL) return 0;
Node *prev = NodeAt(L, i - 1);
q->next = prev->next;
prev->next = q;
L->length++;
return 1;
}Get用的是NodeAt，不用改。Locate的遍历改成从L->head->next开始，跳过头结点。上面的main也要把打印循环的起点改成L.head->next，否则会把头结点里那个'\0'也打印出来；改完输出仍是caxt。从现在起都用头结点版本。
2.9.5 删除第i个元素与再次测试
以把刚插进去的x再删掉为例，即Delete(L, 2)，caxt回到cat。同样不挪动任何结点，只改一个地址：让a的next越过x直接指向t。然后x这个结点没人指向了，把它的空间还给系统。
和插入一样，第一步先要找到前一个结点a。现在有了头结点，head指向头结点，NodeAt(L, 1)从头结点出发走两步到a。假设头结点在116号。
改之前，就是插入完成的样子，前面多了头结点：
text
head = 116
│
▼
┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐
│ │ 100 │────►│ c │ 108 │────►│ a │ 102 │────►│ x │ 104 │────►│ t │ 0 │
└───┴─────┘ └───┴─────┘ └───┴─────┘ └───┴─────┘ └───┴─────┘
116 100 108 102 104
头结点 prev q第二步，用q记住要删的结点x（它是prev的next）。第三步，把a的右格从102改成104——这个104在x的右格里，抄过来：
text
head = 116
│
▼
┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐
│ │ 100 │────►│ c │ 108 │────►│ a │ 104 │────────────────────►│ t │ 0 │
└───┴─────┘ └───┴─────┘ └───┴─────┘ ┌───┬─────┐ └───┴─────┘
116 100 108 │ x │ 104 │ 104
头结点 prev └───┴─────┘
102
qx还在102号，右格还记着104，但从head出发已经走不到它了：116→100→108→104，读出cat。第四步，把102号的空间free掉。这正是插入的后两步倒着走：插入是把t的地址从a抄给x、再让a指向x；删除是把t的地址从x抄回a、再释放x。
第二步"用q记住x"不能省。改完a的右格之后，x就没人指向了，如果事先没记下它的地址，就再也找不到它，既拿不到104，也没法释放。
c
int Delete(LinkList *L, int i) {
if (i < 0 || i >= L->length) return 0;
Node *prev = NodeAt(L, i - 1); /* 第一步：找到前一个，i=0时是头结点 */
Node *q = prev->next; /* 第二步：记住要删的 */
prev->next = q->next; /* 第三步：越过q */
free(q); /* 第四步：释放 */
L->length--;
return 1;
}free(q)必须放在最后。释放之后q指向的空间就不属于我们了，再读q->next是错误。先取用、后释放。
如果不用头结点，Delete会和无头结点版的Insert一样需要一个i=0的分支，读者可以自己试着写一写。
再用main跑一遍
把Insert和Delete放在一起测试，打印循环从头结点的下一个开始：
c
int main(void) {
LinkList L;
if (!Init(&L)) return 1;
const char *s = "cat";
for (int i = 0; s[i]; i++) Insert(&L, i, s[i]);
Insert(&L, 2, 'x'); /* caxt */
Delete(&L, 2); /* cat */
for (Node *p = L.head->next; p != NULL; p = p->next)
putchar(p->data);
putchar('\n');
return 0;
}跟踪Delete(&L, 2)：prev = NodeAt(L, 1)，从头结点走两步得到a；q = prev->next是x；prev->next = q->next把x的next（104）赋给a的next；free(q)释放102号；长度变3。程序输出cat。
2.9.6 销毁与完整版本
销毁
链表的结点是一个个申请的，也要一个个释放，包括头结点。遍历时有个陷阱：free掉当前结点后，就不能再从它读next了，所以要先记下下一个再释放当前：
c
void Destroy(LinkList *L) {
Node *p = L->head;
while (p != NULL) {
Node *next = p->next; /* 先记下下一个 */
free(p);
p = next;
}
L->head = NULL;
L->length = 0;
}完整版本
把头结点版本的所有函数放在一起，从现在起本章都用这一套：
c
typedef struct Node {
char data;
struct Node *next;
} Node;
typedef struct {
Node *head; /* 指向头结点 */
int length;
} LinkList;
Node *NewNode(char x) {
Node *p = (Node *)malloc(sizeof(Node));
if (p == NULL) return NULL;
p->data = x;
p->next = NULL;
return p;
}
Node *NodeAt(LinkList *L, int i) { /* 第i个结点，i=-1为头结点 */
Node *p = L->head;
for (int k = -1; k < i; k++)
p = p->next;
return p;
}
int Init(LinkList *L) {
L->head = NewNode('\0');
if (L->head == NULL) return 0;
L->length = 0;
return 1;
}
int Length(LinkList *L) {
return L->length;
}
char Get(LinkList *L, int i) {
if (i < 0 || i >= L->length) return '\0';
return NodeAt(L, i)->data;
}
int Insert(LinkList *L, int i, char x) {
if (i < 0 || i > L->length) return 0;
Node *q = NewNode(x);
if (q == NULL) return 0;
Node *prev = NodeAt(L, i - 1);
q->next = prev->next;
prev->next = q;
L->length++;
return 1;
}
int Delete(LinkList *L, int i) {
if (i < 0 || i >= L->length) return 0;
Node *prev = NodeAt(L, i - 1);
Node *q = prev->next;
prev->next = q->next;
free(q);
L->length--;
return 1;
}
int Locate(LinkList *L, char x) {
int i = 0;
for (Node *p = L->head->next; p != NULL; p = p->next, i++)
if (p->data == x) return i;
return -1;
}
void Destroy(LinkList *L) {
Node *p = L->head;
while (p != NULL) {
Node *next = p->next;
free(p);
p = next;
}
L->head = NULL;
L->length = 0;
}对照2.4.4的顺序表版本：六个操作的函数名、参数、返回值完全相同，只是类型从SeqList换成了LinkList。这就是下一节能把编辑器原样搬过来的前提。
到这里你有了：头结点版单链表的六个操作，以及一个从空表造出
cat、插入再删除的测试程序。 接口：和顺序表的六个函数完全相同。 下一步：把编辑器原样搬到链表上。