2.12 光标记住结点：双向链表，编辑器2.1与2.2

2.12.1 把光标改成结点指针

上一节的结论是：链表插入删除本身O(1)，慢在每次从头走到位置。而编辑器的光标一直停在编辑位置附近，没有理由每敲一个键都从头重走一遍。让光标直接记住结点，而不是记一个整数。

光标记哪个结点？编辑器的插入点在|处，|前面那个字符的结点就是"插入时的前一个结点"，让光标指向它最方便：敲字符就是在光标结点后面插入，然后光标移到新结点上。光标在行首时，|前面没有字符，让它指向头结点——这正是头结点的用处，行首不再特殊。

                                cursor
                                  │
                                  ▼
┌───┬───┐     ┌───┬───┐     ┌───┬───┐     ┌───┬───┐
│   │ ●─┼────►│ c │ ●─┼────►│ a │ ●─┼────►│ t │ ╱ │
└───┴───┘     └───┴───┘     └───┴───┘     └───┴───┘
 头结点

屏幕显示：ca|t

2.12.2 结点位置操作集：先在单链表上实现

有一个问题。现在的Insert(L, i, x)、Delete(L, i)只接受整数位置，编辑器手里拿着的是结点指针，没法调用它们。这不是链表的问题，是2.2节定义操作集时默认了"位置就是整数"。这个默认对顺序表天然合适，对链表就不合适了。

所以要给线性表增加一组以结点为位置的操作。按编辑器的需求来定：敲字符要"在光标后面插入"，退格要"删掉光标这个结点"，左移右移要"前一个、后一个"，显示要"从头开始逐个取"。六个操作：

操作	含义
Head(L)	头结点，即第0个元素之前的位置
Next(p)	p的后一个位置
Prev(L, p)	p的前一个位置
Data(p)	p处的元素
InsertAfter(L, p, x)	在p后面插入x
DeleteNode(L, p)	删除p这个结点，p不能是头结点

先在现有的单链表上实现。前四个和InsertAfter都很直接，InsertAfter就是2.9节Insert去掉定位那一段：

Node *Head(LinkList *L) { return L->head; }
Node *Next(Node *p)     { return p->next; }
char  Data(Node *p)     { return p->data; }

int InsertAfter(LinkList *L, Node *p, char x) {
    Node *q = NewNode(x);
    if (q == NULL) return 0;
    q->next = p->next;
    p->next = q;
    L->length++;
    return 1;
}

Prev和DeleteNode就没这么顺利。单链表的结点只记着后一个，前一个在哪没有任何记录，Prev唯一的办法是从头结点开始走，走到某个结点的next等于p为止。DeleteNode要把p从链上摘下来，必须改p前一个结点的next，所以它也得先调Prev：

Node *Prev(LinkList *L, Node *p) {     /* 单链表上只能从头走 */
    Node *q = L->head;
    while (q->next != p) q = q->next;
    return q;
}

int DeleteNode(LinkList *L, Node *p) {
    Node *prev = Prev(L, p);           /* 这一步是O(n)的 */
    prev->next = p->next;
    free(p);
    L->length--;
    return 1;
}

要看清楚：这两个函数从外面看和其他操作一样，一次调用；但里面各藏着一个从头走的循环，O(n)。接口对了，代价还在。

顺便说明，原来的六个整数位置操作一个不少，而且可以用新操作改写：Insert(L, i, x)就是InsertAfter(L, NodeAt(L, i−1), x)，Delete(L, i)就是DeleteNode(L, NodeAt(L, i))。两套接口是一套东西。

还要说明的是，2.10节能做到"main一行不改"，是因为只换了实现、没动接口；这次main要改，是因为接口变了。接口本身也会影响效率，2.13节会回头讨论。

2.12.3 编辑器2.1

main只用这六个操作。光标是Node *cursor，初始指向头结点：

void Show(LinkList *L, Node *cursor) {
    if (cursor == Head(L)) putchar('|');
    for (Node *p = Next(Head(L)); p != NULL; p = Next(p)) {
        putchar(Data(p));
        if (p == cursor) putchar('|');
    }
    putchar('\n');
}

int main(void) {
    LinkList text;
    Node *cursor;
    char cmd, ch;

    if (!Init(&text)) return 1;
    cursor = Head(&text);                     /* 行首 */
    while (scanf(" %c", &cmd) == 1 && cmd != 'q') {
        switch (cmd) {
        case 'i':
            scanf(" %c", &ch);
            if (ch == '_') ch = ' ';
            if (InsertAfter(&text, cursor, ch)) cursor = Next(cursor);
            else printf("插入失败\n");
            break;
        case 'd':
            if (cursor != Head(&text)) {
                Node *dead = cursor;
                cursor = Prev(&text, cursor);
                DeleteNode(&text, dead);
            }
            break;
        case 'l':
            if (cursor != Head(&text)) cursor = Prev(&text, cursor);
            break;
        case 'r':
            if (Next(cursor) != NULL) cursor = Next(cursor);
            break;
        }
        Show(&text, cursor);
    }
    Destroy(&text);
    return 0;
}

退格里的顺序有讲究：先把光标退到前一个，再删原来的光标结点；反过来先删，就没法再问它的前一个是谁了。

Show现在顺着结点只走一遍，O(n)，上一节O(n²)的问题解决了。

输入前面那段会话，输出仍然是c|、ca|、cat|、ca|t、cax|t、ca|t、cat|。功能对了，再看效率。敲字符是InsertAfter加Next，O(1)；右移是Next，O(1)；显示O(n)。但退格和左移各调用一次Prev，单链表上是O(n)。问题解决了一半。

2.12.4 双向链表

根源是单链表的结点只记后一个。既然如此，让每个结点把前一个也记下来：

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

每个结点三个格子，中间是数据，两边各一个地址。这样的链表叫双向链表。头结点的prev是NULL，最后一个结点的next是NULL：

head
  │
  ▼
┌───┬───┬───┐    ┌───┬───┬───┐    ┌───┬───┬───┐    ┌───┬───┬───┐
│ ╱ │   │ ●─┼───►│ ●─┼ c │ ●─┼───►│ ●─┼ a │ ●─┼───►│ ●─┼ t │ ╱ │
│   │   │   │◄───┼─● │   │   │◄───┼─● │   │   │◄───┼─● │   │   │
└───┴───┴───┘    └───┴───┴───┘    └───┴───┴───┘    └───┴───┴───┘
    头结点

代价是每个结点多占一个地址的空间。换来的是：站在任何一个结点上，前一个和后一个都是一步可达。

接口不变，重写四个实现。NewNode多初始化一个prev：

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

Prev一步完成：

Node *Prev(LinkList *L, Node *p) { return p->prev; }

参数L现在用不上了，保留它是为了签名和单链表版本一致，main不用改。

InsertAfter在p后面插q，要接四根线：q的prev和next，p的next，以及p原来的后一个的prev。p可能是最后一个结点，这时它没有后一个，那一根线不用接：

int InsertAfter(LinkList *L, Node *p, char x) {
    Node *q = NewNode(x);
    if (q == NULL) return 0;
    q->prev = p;                              /* q的前一个是p */
    q->next = p->next;                        /* q的后一个是p原来的后一个 */
    if (p->next != NULL) p->next->prev = q;   /* 那个后一个的前一个改为q */
    p->next = q;                              /* p的后一个改为q */
    L->length++;
    return 1;
}

顺序仍然要注意：前三行都要用到p->next，即p原来的后一个，所以改p->next的那一行放最后。

DeleteNode不再需要从头找前一个：让p的前一个越过p指向p的后一个，让p的后一个（如果有）越过p指回p的前一个，然后释放p。头结点永远不会被删，所以p->prev一定存在：

int DeleteNode(LinkList *L, Node *p) {
    p->prev->next = p->next;
    if (p->next != NULL) p->next->prev = p->prev;
    free(p);
    L->length--;
    return 1;
}

Head、Next、Data、Length、Get、Locate、NodeAt、Destroy都不用改。整数位置的Insert和Delete改成调用新操作，prev指针就自动维护好了：

int Insert(LinkList *L, int i, char x) {
    if (i < 0 || i > L->length) return 0;
    return InsertAfter(L, NodeAt(L, i - 1), x);
}

int Delete(LinkList *L, int i) {
    if (i < 0 || i >= L->length) return 0;
    return DeleteNode(L, NodeAt(L, i));
}

2.12.5 编辑器2.2

main一行不改，再跑一遍

编辑器2.1的main和Show一个字不动，重新编译，输入同一段会话，输出完全相同。这就是编辑器2.2。这次改的是实现、不是接口，所以和2.10节一样，应用层不动。

用这段会话跟踪一遍，看双向链表上光标怎么动：

• i c：光标在头结点，InsertAfter在头结点后面插c：c的prev是头结点、next是NULL，头结点的next改为c；光标移到c。显示c|。
• i a、i t：同理，光标依次到a、t。显示cat|。
• l：光标从t退到Prev(t)，一步读到a。显示ca|t。
• i x：在a后面插x：x的prev是a、next是t，t的prev改为x，a的next改为x；光标到x。显示cax|t。
• d：光标结点是x，先退到Prev(x)即a，再DeleteNode(x)：a的next改为t，t的prev改为a，释放x。显示ca|t。
• r：光标到Next(a)即t。显示cat|。

每一步都只动了光标附近的几根线，和整行有多长没有关系。

时间复杂度

六个结点位置操作在两种链表上的复杂度：

操作	单链表	双向链表
Head、Next、Data	O(1)	O(1)
InsertAfter	O(1)	O(1)
Prev	O(n)	O(1)
DeleteNode	O(n)	O(1)

再把编辑器的几个动作放在一起，和之前的版本比：

动作	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(1)	O(1)	O(1)
显示	O(n)	O(n²)	O(n)	O(n)

2.6节提出的问题——在行首打字慢——到这里才真正解决：不管光标在哪，敲一个字符、退格、移动光标都是O(1)。显示O(n)无法避免，n个字符总要一个个打出来。

回头看这一路：换成链表本身并没有让编辑器变快（2.0），让它变快的是"让光标记住结点"这个改动，而它要求接口能表达"结点位置"；接口定对之后，单链表上还有两个操作藏着O(n)，最后为了前后都能一步走，把链表改成了双向。存储结构、接口、应用三者是一起变的。下一节把顺序表和链表放在一起，讨论什么情况下该选哪个。

到这里你有了：双向链表和结点位置操作集，以及敲字符、退格、移动光标都是O(1)的编辑器2.2。 学到的：换存储结构本身不一定变快，接口能不能表达"位置"同样关键。 下一步：把顺序表和链表放在一起比较，看什么场景选哪个。