外观
2.17 双向链表
找前一个结点要从头走
编辑器2.1里,屏幕是cat|,光标记着t结点。按一次l左移,光标要移到t的前一个结点,也就是a结点:
text
L = 120
│
▼
┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐
│ │ 100 │────►│ c │ 109 │────►│ a │ 105 │────►│ t │ 0 │
└───┴─────┘ └───┴─────┘ └───┴─────┘ └───┴─────┘
120 100 109 105
头结点 cursor站在t结点上,往后一步就到:它的地址格记着下一个结点的地址。可t的前一个是谁,t结点里没有任何记录。所以Prev只能从头结点出发,一个一个往后走,直到下一个是t为止。
一行有一千个字符时,光标在行尾按一次左移,就要走一千步。2.16量过,编辑器2.1的左移和退格都要调用Prev,都是O(n)。
本节问题能不能站在一个结点上,一步就找到前一个?
什么是双向链表
往后一步就到,是因为结点记着后一个结点的地址。那么想往前一步就到,就让结点再记一个前一个结点的地址。
每个结点就有了三格:一格前一个结点的地址,一格数据,一格后一个结点的地址。像这样,每个结点都记着前后两个结点地址的链表,叫双向链表。原来只记后一个的,叫单链表。
一个双向链表,就是一串前后都用地址连起来的结点,加上一个头指针。cat存成双向链表是这样:
text
L = 120
│
▼
┌─────┬───┬─────┐ ┌─────┬───┬─────┐ ┌─────┬───┬─────┐ ┌─────┬───┬─────┐
│ │ │ ├────►│ │ │ ├────►│ │ │ ├────►│ │ │ │
│ 0 │ │ 100 │ │ 120 │ c │ 109 │ │ 100 │ a │ 105 │ │ 109 │ t │ 0 │
│ │ │ │◄────┤ │ │ │◄────┤ │ │ │◄────┤ │ │ │
└─────┴───┴─────┘ └─────┴───┴─────┘ └─────┴───┴─────┘ └─────┴───┴─────┘
120 100 109 105
头结点每个结点三格,从左到右是前一个结点的地址、数据、后一个结点的地址。向右的箭头从后一个地址格伸出,指向后一个结点;向左的箭头从前一个地址格伸出,指向前一个结点。头结点前面没有结点,它的前一个地址是0,也就是NULL;t是最后一个,它的后一个地址是0。
回到开头的问题。站在t结点上,读它的前一个地址,得到109,一步就到a结点。不管表有多长,找前一个都只要一步。
代价是每个结点多占一个地址格的空间。
用C语言表示,结构体多一个成员prior,三个成员的顺序和图里一样:
c
typedef struct Node {
struct Node *prior; /* 前一个结点的地址 */
char data; /* 数据格 */
struct Node *next; /* 后一个结点的地址 */
} Node, *LinkList;类型名仍然是Node和LinkList,和单链表一样。
双向链表的插入
屏幕是ca|t,敲x,要变成cax|t。光标记着a结点,调用的是InsertAfter(L, a结点, 'x')。变化都在a、t之间,图里只画这两个结点,前面的用省略号表示。操作前:
text
┌─────┬───┬─────┐ ┌─────┬───┬─────┐
...─►│ │ │ ├────►│ │ │ │
│ 100 │ a │ 105 │ │ 109 │ t │ 0 │
...◄─┤ │ │ │◄────┤ │ │ │
└─────┴───┴─────┘ └─────┴───┴─────┘
109 105
p要达到的样子,假设x结点放在102号:
text
┌─────┬───┬─────┐ ┌─────┬───┬─────┐ ┌─────┬───┬─────┐
...─►│ │ │ ├────►│ │ │ ├────►│ │ │ │
│ 100 │ a │ 102 │ │ 109 │ x │ 105 │ │ 102 │ t │ 0 │
...◄─┤ │ │ │◄────┤ │ │ │◄────┤ │ │ │
└─────┴───┴─────┘ └─────┴───┴─────┘ └─────┴───┴─────┘
109 102 105对照两张图,变了四处:多了x结点,它的前一个地址是109,后一个地址是105;a的后一个地址从105变成102;t的前一个地址从109变成102。单链表插入只改两处,多出来的两处,都是前一个地址。
第一步:申请x结点。假设得到102号,数据格写x。两个地址格还没写,内容不知道:
c
Node *q = (Node *)malloc(sizeof(Node)); /* 102号 */
q->data = 'x';text
┌─────┬───┬─────┐ ┌─────┬───┬─────┐
...─►│ │ │ ├────►│ │ │ │
│ 100 │ a │ 105 │ │ 109 │ t │ 0 │
...◄─┤ │ │ │◄────┤ │ │ │
└─────┴───┴─────┘ └─────┴───┴─────┘
109 105
p
┌─────┬───┬─────┐
│ │ │ │
│ ? │ x │ ? │
│ │ │ │
└─────┴───┴─────┘
102
q第二步:让x结点指向t结点。t的地址105正记在a的后一个地址格里,也就是p->next,抄给x:
c
q->next = p->next; /* x 的 next 写 105 */text
┌─────┬───┬─────┐ ┌─────┬───┬─────┐
...─►│ │ │ ├────►│ │ │ │
│ 100 │ a │ 105 │ │ 109 │ t │ 0 │
...◄─┤ │ │ │◄────┤ │ │ │
└─────┴───┴─────┘ └─────┴───┴─────┘
109 ▲ 105
p │
┌─────┬───┬──┴──┐
│ │ │ │
│ ? │ x │ 105 │
│ │ │ │
└─────┴───┴─────┘
102
q第三步:让x结点指回a结点。x的前一个就是p,也就是109号:
c
q->prior = p; /* x 的 prior 写 109 */text
┌─────┬───┬─────┐ ┌─────┬───┬─────┐
...─►│ │ │ ├────►│ │ │ │
│ 100 │ a │ 105 │ │ 109 │ t │ 0 │
...◄─┤ │ │ │◄────┤ │ │ │
└─────┴───┴─────┘ └─────┴───┴─────┘
109 ▲ ▲ 105
p │ │
┌──┴──┬───┬──┴──┐
│ │ │ │
│ 109 │ x │ 105 │
│ │ │ │
└─────┴───┴─────┘
102
q第四步:让t结点指回x结点。t的前一个地址从109改成102。t要通过a的后一个地址格找到,p->next现在还是105,所以写成p->next->prior:
c
p->next->prior = q; /* t 的 prior 改成 102 */text
┌─────┬───┬─────┐ ┌─────┬───┬─────┐
...─►│ │ │ ├────►│ │ │ │
│ 100 │ a │ 105 │ │ 102 │ t │ 0 │
...◄─┤ │ │ │ │ │ │ │
└─────┴───┴─────┘ └───┬─┴───┴─────┘
109 ▲ ▲ │ 105
p │ │ ▼
┌──┴──┬───┬──┴──┐
│ │ │ │
│ 109 │ x │ 105 │
│ │ │ │
└─────┴───┴─────┘
102
q第五步:让a结点指向x结点。a的后一个地址从105改成102:
c
p->next = q; /* a 的 next 改成 102 */text
┌─────┬───┬─────┐ ┌─────┬───┬─────┐
...─►│ │ │ │ │ │ │ │
│ 100 │ a │ 102 │ │ 102 │ t │ 0 │
...◄─┤ │ │ │ │ │ │ │
└─────┴───┴──┬──┘ └───┬─┴───┴─────┘
109 │▲ ▲ │ 105
p ▼│ │ ▼
┌──┴──┬───┬──┴──┐
│ │ │ │
│ 109 │ x │ 105 │
│ │ │ │
└─────┴───┴─────┘
102
q从a往后读:a、x、t。从t往前读:t、x、a。和要达到的样子一样。
第二步和第四步,都要通过p->next找到t。105只记在a的后一个地址格里,改p->next的第五步必须放在最后,否则t就找不到了。
写成函数。把x换成参数x,就是双向链表的InsertAfter。和2.16单链表的InsertAfter比,多了第三步、第四步两行,都是写前一个地址:
c
int InsertAfter(LinkList *L, Node *p, char x) {
Node *q = (Node *)malloc(sizeof(Node)); /* 申请新结点 */
if (q == NULL) return 0;
q->data = x;
q->next = p->next; /* 新结点指向后一个 */
q->prior = p; /* 新结点指回p */
if (p->next != NULL)
p->next->prior = q; /* 后一个指回新结点 */
p->next = q; /* p指向新结点 */
return 1;
}在末尾插入。cat|敲s,是插在t结点后面。t后面没有结点,第四步没有"后一个"可改,要跳过。所以第四步前面加了if (p->next != NULL)。其余各步照旧:第二步s的后一个地址得到NULL,正好是结束标记。
其他操作的变化
每个结点多了一个前一个地址。凡是改链的操作,都要把它一起维护好;只读不改的操作,不用动。逐个看。
删除:DeleteAfter。屏幕是cax|t,按退格,要删x,也就是a后面那个结点。删除正好是插入反过来:操作前是上一页"要达到的样子",操作后是上一页的"操作前"。变的是两格,a的后一个地址改回105,t的前一个地址改回109:
text
┌─────┬───┬─────┐ ┌─────┬───┬─────┐
...─►│ │ │ ├────►│ │ │ │
│ 100 │ a │ 105 │ │ 109 │ t │ 0 │
...◄─┤ │ │ │◄────┤ │ │ │
└─────┴───┴─────┘ └─────┴───┴─────┘
109 105
p和单链表比,多了改t的那一行。被删的是最后一个结点时,后面没有结点,这一行跳过:
c
int DeleteAfter(LinkList *L, Node *p) {
if (p->next == NULL) return 0; /* p后面没有结点 */
Node *q = p->next; /* 记下要删的结点 */
p->next = q->next; /* 越过它 */
if (q->next != NULL)
q->next->prior = p; /* 后一个指回p */
free(q); /* 还给系统 */
return 1;
}找前一个:Prev。不用从头走了,直接读前一个地址,O(1):
c
Node *Prev(LinkList *L, Node *p) { return p->prior; }参数L用不上了,保留是为了和单链表的版本一样,编辑器不用改。
初始化。头结点前面没有结点,它的前一个地址也要置为NULL,多一行:
c
(*L)->prior = NULL; /* 头结点前面没有结点 */按位序的插入、删除:Insert、Delete。它们也改链,也要维护前一个地址。2.16说过,Insert就是先从头结点走i步,再InsertAfter。现在正好这样写,走到之后直接调用InsertAfter、DeleteAfter,维护前一个地址的代码就只写在一处:
c
int Insert(LinkList *L, int i, char x) {
if (i < 0) return 0;
Node *prev = *L; /* 从头结点出发,走i步 */
for (int k = 0; k < i && prev != NULL; k++)
prev = prev->next;
if (prev == NULL) return 0;
return InsertAfter(L, prev, x); /* 接在prev后面 */
}
int Delete(LinkList *L, int i) {
if (i < 0) return 0;
Node *prev = *L; /* 从头结点出发,走i步 */
for (int k = 0; k < i && prev != NULL; k++)
prev = prev->next;
if (prev == NULL) return 0;
return DeleteAfter(L, prev); /* 删prev后面那个 */
}不用改的操作。求长度、取元素、销毁、Head、Next、Data,都只顺着后一个地址读,不改链,一个字不改。
按结点的六个操作,在两种链表上:
| 操作 | 单链表 | 双向链表 |
|---|---|---|
| Head、Next、Data | O(1) | O(1) |
| InsertAfter、DeleteAfter | O(1) | O(1) |
| Prev | O(n) | O(1) |
编辑器2.2
把编辑器2.1换成双向链表,main和Show要改多少?
先预测。2.15立过规矩:编辑器只调用操作,不碰存储结构。2.16的main和Show只调用Head、Next、Prev、Data、InsertAfter、DeleteAfter,再加上Init、Destroy。这些操作的名字、参数、返回值一个都没变,类型名也还是Node和LinkList。所以预测:main和Show一个字都不用改。
验证。把2.16的main和Show原样接在双向链表的操作后面,编译运行,输入2.6的那段会话:
text
i c c|
i a ca|
i t cat|
l ca|t
i x cax|t
d ca|t
r cat|
q输出逐行相同,预测成立。这就是编辑器2.2。
编辑器的四个版本放在一起:
| 指令 | 1.1 顺序表 | 2.0 链表 | 2.1 按结点 | 2.2 双向链表 |
|---|---|---|---|---|
| 敲字符 | O(n) | O(n) | O(1) | O(1) |
| 退格 | O(n) | O(n) | O(n) | O(1) |
| 左移 | O(1) | O(1) | O(n) | O(1) |
| 右移 | O(1) | O(n) | O(1) | O(1) |
| 显示 | O(n) | O(n²) | O(n) | O(n) |
2.7提出的问题,在行首打字慢,到这里才真正解决:不管光标在哪,敲字符、退格、左移、右移都是O(1)。显示是O(n),n个字符总要一个个打出来。
回头看这一路。换成链表,编辑器并没有变快。改成按结点操作,往后的指令快了。再换成双向链表,往前的指令也快了。代价是每个结点多一个地址格。
练习1:插入x后,四个地址格是多少?
填空
a结点在109号,t结点在105号,x结点在102号。在a和t之间插入x之后:
- x的前一个地址是 ,后一个地址是
- t的前一个地址是
- a的后一个地址是
x夹在a和t中间,前一个是a,后一个是t。t的前一个、a的后一个,都从对方改成了x。
练习2:先改a的后一个地址,会怎样?
单选
有人把插入的第五步挪到了第二步前面:
c
p->next = q; /* a 的 next 改成 102 */
q->next = p->next;
q->prior = p;
if (p->next != NULL)
p->next->prior = q;在a和t之间插入x,会怎样?
A
x的后一个地址抄到的是102,指向它自己,t再也找不到了
B
结果和原来一样,顺序无所谓
第二步要抄的是t的地址105,可它只记在a的后一个地址格里,已经被改成102。
C
t的前一个地址正确改成了102
第四步通过p->next找t,p->next已经是x,改的是x自己的前一个地址。
105只记在a的后一个地址格里。第二步、第四步都要用它找t,所以改p->next必须放在最后。
练习3:退格删x,改了哪两格?
填空
屏幕是cax|t,a在109号,x在102号,t在105号。按一次退格删掉x:
- a的后一个地址改成
- t的前一个地址改成
删除是插入反过来:a越过x指向t,t越过x指回a,再把x还给系统。
双向链表版的完整代码
把这一节的结点类型和操作,2.14没有改动的求长度、取元素、销毁,再加上2.16的Show和main放在一起,就是编辑器2.2的完整程序:
c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
struct Node *prior; /* 前一个结点的地址 */
char data; /* 数据格 */
struct Node *next; /* 后一个结点的地址 */
} Node, *LinkList;
int Init(LinkList *L) {
*L = (Node *)malloc(sizeof(Node)); /* 申请头结点 */
if (*L == NULL) return 0;
(*L)->prior = NULL; /* 头结点前面没有结点 */
(*L)->next = NULL; /* 空表 */
return 1;
}
int Length(LinkList *L) {
int n = 0;
for (Node *p = (*L)->next; p != NULL; p = p->next) /* 跳过头结点 */
n++;
return n;
}
char Get(LinkList *L, int i) {
if (i < 0) return '\0';
Node *p = (*L)->next; /* 跳过头结点 */
for (int k = 0; k < i && p != NULL; k++)
p = p->next;
if (p == NULL) return '\0';
return p->data;
}
void Destroy(LinkList *L) {
Node *p = *L; /* 从头结点开始,全部释放 */
while (p != NULL) {
Node *next = p->next;
free(p);
p = next;
}
*L = NULL;
}
Node *Head(LinkList *L) { return *L; }
Node *Next(Node *p) { return p->next; }
Node *Prev(LinkList *L, Node *p) { return p->prior; }
char Data(Node *p) { return p->data; }
int InsertAfter(LinkList *L, Node *p, char x) {
Node *q = (Node *)malloc(sizeof(Node)); /* 申请新结点 */
if (q == NULL) return 0;
q->data = x;
q->next = p->next; /* 新结点指向后一个 */
q->prior = p; /* 新结点指回p */
if (p->next != NULL)
p->next->prior = q; /* 后一个指回新结点 */
p->next = q; /* p指向新结点 */
return 1;
}
int DeleteAfter(LinkList *L, Node *p) {
if (p->next == NULL) return 0; /* p后面没有结点 */
Node *q = p->next; /* 记下要删的结点 */
p->next = q->next; /* 越过它 */
if (q->next != NULL)
q->next->prior = p; /* 后一个指回p */
free(q); /* 还给系统 */
return 1;
}
int Insert(LinkList *L, int i, char x) {
if (i < 0) return 0;
Node *prev = *L; /* 从头结点出发,走i步 */
for (int k = 0; k < i && prev != NULL; k++)
prev = prev->next;
if (prev == NULL) return 0;
return InsertAfter(L, prev, x); /* 接在prev后面 */
}
int Delete(LinkList *L, int i) {
if (i < 0) return 0;
Node *prev = *L; /* 从头结点出发,走i步 */
for (int k = 0; k < i && prev != NULL; k++)
prev = prev->next;
if (prev == NULL) return 0;
return DeleteAfter(L, prev); /* 删prev后面那个 */
}
void Show(LinkList *L, Node *cursor) {
if (cursor == Head(L)) printf("|");
for (Node *p = Next(Head(L)); p != NULL; p = Next(p)) {
printf("%c", Data(p));
if (p == cursor) printf("|");
}
printf("\n");
}
int main(void) {
LinkList L;
Node *cursor;
char cmd, ch;
if (!Init(&L)) return 1;
cursor = Head(&L); /* 行首 */
while (scanf(" %c", &cmd) == 1 && cmd != 'q') {
switch (cmd) {
case 'i':
scanf(" %c", &ch);
if (ch == '_') ch = ' ';
if (InsertAfter(&L, cursor, ch)) cursor = Next(cursor);
else printf("插入失败\n");
break;
case 'd':
if (cursor != Head(&L)) {
Node *prev = Prev(&L, cursor);
DeleteAfter(&L, prev);
cursor = prev;
}
break;
case 'l':
if (cursor != Head(&L)) cursor = Prev(&L, cursor);
break;
case 'r':
if (Next(cursor) != NULL) cursor = Next(cursor);
break;
}
Show(&L, cursor);
}
Destroy(&L);
return 0;
}到这里你有了双向链表,以及敲字符、退格、左移、右移都是O(1)的编辑器2.2。下一步有些数据本来就首尾相接,比如歌单的列表循环,链表怎样表示?