第 2 章线性表

408 数据结构第 2 章线性表复习讲义，涵盖核心概念、重点考点与典型题型。

一、先建立整章框架

这一章其实围绕一个问题：

逻辑上是一串前后相邻的数据，到底怎样存进计算机？

逻辑结构都是同一个：

a1 → a2 → a3 → ... → an

但可以有两种完全不同的物理实现。

1. 顺序存储

内存：
┌────┬────┬────┬────┐
│ a1 │ a2 │ a3 │ a4 │
└────┴────┴────┴────┘
地址连续

这就是顺序表。

最大特点：

可以直接算出第几个元素在哪里。

所以随机访问快。

2. 链式存储

[a1 | next] → [a2 | next] → [a3 | next] → ...

实际内存地址可能完全不连续：

1000: a1 → 8000
8000: a2 → 3000
3000: a3 → NULL

这就是链表。

最大特点：

不靠物理位置表示先后关系，而靠指针。

所以插入删除灵活。

资料把链式结构进一步分成：

单链表
双链表
循环链表
静态链表

其中前三种通常通过指针实现，静态链表用数组下标模拟指针。

二、2.1 线性表的定义和基本操作

1. 什么叫线性表？

定义：

L = (a_{1}, a_{2}, \dots, a_{n})

其中：

元素数量有限；
元素类型相同；
有明确先后顺序；
除第一个元素外，每个元素只有一个直接前驱；
除最后一个元素外，每个元素只有一个直接后继。

因此它是一种典型的一对一逻辑结构。

一个特别容易混淆的问题

线性表 ≠ 顺序表。

准确来说：

线性表
   ↓
逻辑结构

而：

顺序表
链表
   ↓
存储结构

例如：

逻辑：
A → B → C → D

可以存成数组：

[A][B][C][D]

也可以存成链表：

[A|·] → [B|·] → [C|·] → [D|NULL]

所以：

算法研究逻辑关系，具体代码实现依赖存储结构。

2. 线性表有哪些基本操作？

资料列出的标准操作要熟悉：

InitList(&L)       // 初始化
Length(L)          // 求表长
LocateElem(L,e)    // 按值查找
GetElem(L,i)       // 按位查找
ListInsert(&L,i,e) // 插入
ListDelete(&L,i,&e)// 删除
PrintList(L)       // 输出
Empty(L)           // 判空
DestroyList(&L)    // 销毁

真正考试高频的其实集中在四个：

查找、插入、删除、遍历。

其他操作大多是它们的组合。

三、2.2 顺序表——★★★★★ 高频

资料明确标出“顺序表的应用”为多次算法题考点，因此这一部分必须重点掌握。

1. 顺序表的本质

顺序表就是：

用一段连续的内存空间按逻辑顺序依次存放元素。

假设：

a1  a2  a3  a4

每个元素占 $w$ 个字节。

若第一个元素地址为 $LOC (A)$ ，则第 $i$ 个元素：

LOC (a_{i}) = LOC (A) + (i - 1) w

这条公式解释了为什么顺序表能随机访问。

因为不用：

a1 → a2 → a3 → ...

一个一个找。

只要知道 $i$ ，直接计算地址即可。

所以：

T_{按位访问} = O (1)

2. 位序和数组下标——408 高频坑

线性表：

第1个 第2个 第3个

数组：

data[0] data[1] data[2]

所以始终记住：

数组下标 = 位序 - 1

也就是说：

第 i 个元素 = data[i - 1]

这是本章代码最常见的下标错误之一。

3. 静态顺序表与动态顺序表

静态分配

#define MaxSize 50

typedef struct {
    ElemType data[MaxSize];
    int length;
} SqList;

特点：

最大容量一开始就确定。

例如：

MaxSize = 50
length = 18

意味着：

已经用了18个
还能放32个

如果：

length == MaxSize

继续插入就失败。

动态分配

typedef struct {
    ElemType *data;
    int MaxSize;
    int length;
} SeqList;

通过：

L.data =
(ElemType *)malloc(sizeof(ElemType) * InitSize);

动态申请空间。

很重要的理解

动态顺序表仍然是顺序表。

不是链表。

因为它仍然要求：

[a1][a2][a3][a4]

物理连续。

只是当空间不够时，可以：

申请更大的连续空间
       ↓
复制原数组
       ↓
释放旧空间

资料也特别提醒：动态分配改变的是容量管理方式，并不改变顺序存储的物理结构。

四、顺序表插入——★★★★★

这是必须会手写的基本操作。

假设：

A B C D E

现在在第 3 个位置插入 X：

A B X C D E

问题是：

C D E

必须向后移动。

1. 为什么必须从后向前移动？

原数组：

下标
0 1 2 3 4
A B C D E

插入 X 到第 3 位，即：

data[2]

必须：

E → 5
D → 4
C → 3

最后：

X → 2

所以移动方向必须：

从右往左。

否则，如果从左向右：

C → D位置

原 D 被覆盖。

然后：

D → E位置

但 D 已经没了。

因此资料代码写成：

for (int j = L.length; j >= i; j--)
    L.data[j] = L.data[j - 1];

L.data[i - 1] = e;
L.length++;

2. 为什么循环条件是 `j >= i`？

假设：

length = 5
i = 3

移动：

data[4] → data[5]
data[3] → data[4]
data[2] → data[3]

也就是：

j = 5,4,3

所以：

j >= i

五、顺序表插入复杂度——★★★★★

设原来有 $n$ 个元素。

最好情况

插到最后：

A B C D | X

不移动元素。

所以：

T_{best} = O (1)

最坏情况

插到最前：

X A B C D

所有 $n$ 个元素都移动。

所以：

T_{worst} = O (n)

平均情况

插入位置共：

n + 1

种。

在第 $i$ 个位置，需要移动：

n - i + 1

个元素。

假定各位置等概率，则平均移动次数：

\frac{1}{n + 1} i = 1 \sum n + 1 (n - i + 1)

即：

\frac{1}{n + 1} \cdot \frac{n ( n + 1 )}{2} = \frac{n}{2}

因此：

T_{avg} = O (n)

这一类“平均移动多少元素”的题非常适合选择题。资料也明确把顺序表基本操作复杂度列为 2023 年考点。

六、顺序表删除——★★★★★

例如：

A B C D E

删除 C：

A B D E

这次需要：

D E

向前移动。

所以方向反过来：

从左往右。

核心代码：

e = L.data[i - 1];

for (int j = i; j < L.length; j++)
    L.data[j - 1] = L.data[j];

L.length--;

删除复杂度

删除第 $i$ 个元素：

需要移动：

n - i

个元素。

最好

删最后一个：

O (1)

最坏

删第一个：

O (n)

平均移动次数

\frac{1}{n} i = 1 \sum n (n - i)

所以：

\frac{1}{n} \cdot \frac{n ( n - 1 )}{2} = \frac{n - 1}{2}

因此：

T_{avg} = O (n)

七、顺序表查找

这里一定要区分两个概念。

1. 按位查找

问：

第 $i$ 个元素是什么？

由于：

A [i - 1]

可以直接访问：

O (1)

2. 按值查找

问：

值为 $e$ 的元素在哪？

如果表没有其他条件：

从头比较：
A[0]
A[1]
A[2]
...

所以平均：

O (n)

最坏：

O (n)

如果顺序表有序呢？

就可以折半查找。

因此：

O (lo g_{2} n)

这一点是顺序表相比普通链表的重要优势。

因为折半查找需要直接访问：

中间元素

顺序表：

A[mid]

即可。

链表则不能直接得到第 mid 个结点。

八、顺序表最核心的考试理解

可以记成四个字：

查快，改慢。

按位置访问：

O (1)

插入删除：

O (n)

原因：

地址连续
↓
可以直接算位置
↓
但改变位置需要整体搬家

九、2.3 单链表——★★★★★ 整章核心

资料的考点追踪显示，单链表应用在多届统考中反复出现，因此这是第 2 章最重要的部分之一。

1. 单链表结点

typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

每个结点：

┌──────┬──────┐
│ data │ next │
└──────┴──────┘

其中：

data：数据
next：下一个结点地址

2. 为什么链表不需要连续地址？

例如：

地址1000：
[A | 5000]

地址5000：
[B | 2600]

地址2600：
[C | NULL]

逻辑结构仍然是：

A → B → C

因为：

A.next = 5000
B.next = 2600

所以链表的本质就是：

用指针代替物理相邻关系。

十、头指针、头结点——★★★★★ 高频易错

这一部分经常混。

1. 头指针

头指针：

指向链表第一个结点的指针。

例如：

L
↓
[A] → [B] → [C]

这里 L 是头指针。

2. 头结点

人为增加一个结点：

L
↓
[head] → [A] → [B] → [C]

head 本身通常不存有效数据。

此时：

L 指向头结点
L->next 指向第一个数据结点

3. 带头结点空表

L
↓
[head | NULL]

判空：

L->next == NULL

4. 不带头结点空表

L == NULL

十一、为什么要加头结点？

这是非常重要的“为什么”。

假设没有头结点：

L → A → B → C

现在在 A 前面插 X：

L → X → A → B → C

必须修改：

L = X;

但如果是在 B 前插 X：

A → X → B

只修改普通结点指针即可。

也就是说：

首结点操作和普通结点操作不统一。

加入头结点以后：

L → head → A → B → C

在 A 前插 X：

head → X → A

本质与：

A → X → B

完全一样。

因此头结点最大的价值是：

统一边界操作。

资料明确强调了这一点。

十二、单链表查找

1. 按位查找

想找第 $i$ 个数据结点。

由于链表不能随机访问：

head → a1 → a2 → ... → ai

必须一个一个走。

因此：

O (n)

核心形式：

LNode *p = L->next;
int j = 1;

while (p != NULL && j < i) {
    p = p->next;
    j++;
}

2. 按值查找

LNode *p = L->next;

while (p != NULL && p->data != e)
    p = p->next;

也是：

O (n)

十三、单链表插入——★★★★★

假设：

p → A → B

在 A 后插入 X：

p → A → X → B

设：

p 指向 A
s 指向 X

核心两句：

s->next = p->next;
p->next = s;

为什么顺序不能反？

原来：

p
↓
A ─────→ B

第一步：

s->next = p->next;

变成：

A → B
X → B

第二步：

p->next = s;

得到：

A → X → B

如果反过来：

p->next = s;
s->next = p->next;

执行第一句后：

A → X

原来的 B 地址已经丢了。

第二句此时：

s->next = s;

于是：

X → X

形成自环。

模拟题也专门考过这一点：带头结点链表用头插法时，正确顺序是先令新结点指向原首结点，再令头结点指向新结点。

十四、为什么“已知 p 后插”是 $O (1)$ ，而“第 i 位插入”是 $O (n)$ ？

这是一个非常容易答错的问题。

如果题目说：

已知结点 p，在 p 后插入。

只需要：

s->next = p->next;
p->next = s;

所以：

O (1)

但是如果说：

在第 $i$ 个位置插入。

你首先要找到第 $i - 1$ 个结点：

head → 1 → 2 → ... → i-1

查找本身：

O (n)

虽然修改指针只有：

O (1)

总复杂度仍是：

O (n)

所以考试中必须看清楚：

操作位置是否已经给出。

十五、单链表前插的 $O (1)$ 技巧

假设题目给你结点：

p
↓
A → B

要求：

在 p 前插入 X。

单链表没有 prior 指针。

普通做法必须从头找前驱：

O (n)

但资料给出了一个非常巧妙的技巧。

先在 p 后插新结点：

A → X → B

然后交换 A、X 的数据：

X → A → B

从逻辑数据序列看：

X
A
B

就相当于在原 A 前插入 X。

代码：

s->next = p->next;
p->next = s;

ElemType temp = p->data;
p->data = s->data;
s->data = temp;

因此若数据可复制，可实现：

O (1)

这是很典型的“改数据代替改结构”思想。

十六、单链表删除——★★★★★

假设：

A → B → C

删除 B。

设：

p 指向 A
q 指向 B

只需：

q = p->next;
p->next = q->next;
free(q);

图示：

删除前：

p
↓
A → B → C
    ↑
    q

执行：

p->next = q->next;

变为：

A ─────→ C

B

然后：

free(q);

十七、“删除给定结点 p”的 $O (1)$ 技巧——★★★★★

这是链表算法中非常经典的技巧。

假设：

A → B → C → D
    ↑
    p

如果直接删 B，本来需要知道 A。

但单链表中：

不知道前驱 A。

正常必须从头找：

O (n)

技巧

把 C 的数据复制到 B：

A → C → C → D
    ↑
    p

再删除后面的 C：

A → C → D
    ↑
    p

逻辑效果：

原来的 B 消失了。

代码：

LNode *q = p->next;

p->data = q->data;
p->next = q->next;

free(q);

所以：

O (1)

但有一个重要限制

如果：

p
↓
D → NULL

即 p 是尾结点。

就不能这么做，因为：

p->next == NULL

没有后继可以复制。

十八、头插法建立单链表——★★★★★

输入：

1 2 3 4

头插法过程：

先插 1：

head → 1

插 2：

head → 2 → 1

插 3：

head → 3 → 2 → 1

插 4：

head → 4 → 3 → 2 → 1

最终：

4 3 2 1

所以必须牢牢记住：

头插法会逆序。

核心：

s->next = L->next;
L->next = s;

十九、尾插法建立单链表——★★★★★

输入：

1 2 3 4

要求：

1 → 2 → 3 → 4

就必须不断插到尾部。

但如果每次都从头找尾：

O (n)

每个元素一次：

O (n^{2})

所以增加一个尾指针：

LNode *r = L;

每次：

r->next = s;
r = s;

这样每次插入：

O (1)

建立整个表：

O (n)

因此：

尾插法正序，必须维护尾指针。

资料总结也把“头插逆序、尾插正序”列为本章必须掌握的对比。

二十、链表逆置——★★★★★ 算法题核心思想

资料把“逆置法”列为链表算法题常用技巧。

假设：

1 → 2 → 3 → 4 → NULL

逆置：

4 → 3 → 2 → 1 → NULL

经典做法需要三个指针：

pre
p
r

其中：

pre：已经逆置好的部分
p：当前结点
r：保存后继

为什么要保存 r？

假设：

pre    p
 ↓     ↓
1 ←    2 → 3 → 4

如果直接：

p->next = pre;

原来的：

3 → 4

就找不到了。

所以必须先：

r = p->next;

再：

p->next = pre;

最后推进：

pre = p;
p = r;

完整核心：

LNode *pre = NULL;
LNode *p = L->next;
LNode *r;

while (p != NULL) {
    r = p->next;
    p->next = pre;
    pre = p;
    p = r;
}

L->next = pre;

复杂度：

T (n) = O (n)

辅助空间：

S (n) = O (1)

链表题里最重要的原则之一就是：

改 next 之前，先想清楚原来的 next 以后还需不需要。

资料的复习总结也特别强调了“指针修改顺序”这一点。

二十一、2.3.3 双链表——★★★★

单链表最大的缺陷：

只能知道后继，不知道前驱。

所以定义：

typedef struct DNode {
    ElemType data;
    struct DNode *prior;
    struct DNode *next;
} DNode;

结构：

← prior | data | next →

例如：

A ⇄ B ⇄ C

对 B：

B->prior = A
B->next  = C

二十二、双链表插入——★★★★★ 指针顺序题

资料标出 2023 年曾考双链表插入。

现在：

A ⇄ B
↑
p

在 A 后插入 X：

A ⇄ X ⇄ B

设：

p = A
s = X

标准思路：

s->next = p->next;
p->next->prior = s;
s->prior = p;
p->next = s;

理解它，不要死背。

新结点 X 有两个邻居：

A ← X → B

所以：

X.prior = A
X.next  = B

同时：

A.next  = X
B.prior = X

总共就是四根指针。

为什么 `s->next = p->next` 必须在 `p->next = s` 前？

因为：

p->next

原本保存 B 的地址。

如果先：

p->next = s;

那么：

B 的地址就丢了

之后再：

s->next = p->next;

得到的就是：

s->next = s;

因此，本质还是同一句话：

先保存旧关系，再建立新关系。

模拟选择题也专门设置了双向循环链表中“在 p 前插 x”的语句顺序判断。

二十三、双链表删除——★★★★

假设：

A ⇄ B ⇄ C
↑    ↑
p    q

删除 B：

p->next = q->next;
q->next->prior = p;
free(q);

得到：

A ⇄ C

如果直接给出了：

q = B

双链表可以通过：

q->prior

直接得到 A。

因此删除给定结点一般可以做到：

O (1)

而单链表通常还需要找前驱。

二十四、单链表和双链表的本质区别

项目	单链表	双链表
后继	容易	容易
前驱	需遍历	直接得到
指针空间	少	多
插删维护	简单	较复杂
双向遍历	不行	可以

所以：

双链表是用更多空间换更方便的前驱访问。

二十五、2.3.4 循环链表——★★★★

1. 普通单链表

尾结点：

an → NULL

2. 循环单链表

尾结点：

an
 ↓
头结点

即：

head → a1 → a2 → a3
 ↑                ↓
 └────────────────┘

因此：

r->next = L;

二十六、循环链表判空——高频易错

带头结点普通单链表：

L->next == NULL

循环单链表空表：

L
↺

头结点自己指向自己。

所以：

L->next == L

而不是：

L->next == NULL

资料标出“循环单链表删除首元素”在 2021 年出现过考点。

二十七、为什么循环单链表常只设尾指针？

假设：

          r
          ↓
head → A → B → C
 ↑            ↓
 └────────────┘

如果只知道尾指针 r：

尾结点：

第一个结点或头部：

r->next

因此：

找尾部： $O (1)$
找头部： $O (1)$

特别适合需要频繁操作首尾的场景。

模拟题中也会结合“只有尾指针的循环单链表”考出队、入队等复杂度判断。

二十八、循环单链表尾插

原来：

... → r
      ↓
     head

插入 s。

第一步：

s->next = r->next;

即：

s → head

第二步：

r->next = s;

第三步：

r = s;

最终：

旧尾 → 新尾 → head

整个操作：

O (1)

二十九、循环双链表

普通双链表：

NULL ← head ⇄ A ⇄ B ⇄ C → NULL

循环双链表：

        ┌──────────────┐
        ↓              │
head ⇄ A ⇄ B ⇄ C
 ↑              ↓
 └──────────────┘

头结点：

L->prior

指向尾结点。

尾结点：

tail->next

指向头结点。

空循环双链表

   ┌──────┐
   ↓      │
   head
   ↑      │
   └──────┘

因此：

L->next == L
L->prior == L

三十、2.3.5 静态链表——★★

这一部分理解即可，但选择题可能直接考“数组下标模拟指针”。

普通链表：

struct Node {
    data;
    Node *next;
};

静态链表：

struct Node {
    data;
    int next;
};

注意：

next 不是地址

而是：

下一个结点的数组下标。

例如：

下标	data	next
0		2
1	b	6
2	a	1
3	d	-1
6	c	3

从 0 开始：

0.next = 2

所以首数据：

下标2 → a

然后：

2.next = 1

所以：

a → b

再：

1.next = 6

所以：

b → c

最后：

6 → 3 → -1

得到：

a → b → c → d

典型选择题

资料题库中有一道：

若逻辑上第 $k$ 个结点数组下标是 $i$ ，第 $k + 1$ 个结点数据是什么？

因为：

S[i].link

是后继下标。

所以：

S[S[i].link].data

这就是静态链表最核心的考法。

三十一、顺序表 vs 链表——★★★★★ 必背但要理解

这一表建议真正理解。

操作	顺序表	单链表
按位访问	$O (1)$	$O (n)$
无序按值查找	$O (n)$	$O (n)$
有序查找	可折半 $O (lo g n)$	通常仍 $O (n)$
已知位置后插	常需移动 $O (n)$	$O (1)$
删除已知前驱的后继	常需移动 $O (n)$	$O (1)$
存储空间	连续	可不连续
每个元素额外空间	无	需要指针
扩容	不方便	灵活

资料将二者的选择原则总结为：规模稳定、随机访问多时更适合顺序表；规模变化大、插入删除多时更适合链式存储。

三十二、最容易错的一句话

很多人会说：

链表插入删除是 $O (1)$ 。

这句话不完整。

正确说法：

如果插入/删除位置已经确定，修改指针是 $O (1)$ 。

如果题目是：

删除第 $i$ 个元素。

还需要先找：

第 i-1 个结点

所以：

O (n) + O (1) = O (n)

因此实际复杂度必须拆成：

定位成本 + 修改成本

这是本章特别重要的复杂度分析思想。

三十三、本章算法题真正考什么？

资料总结得非常明确：算法设计题通常要求三部分：

写算法思想；
C/C++ 描述；
分析时间、空间复杂度。

而常见技巧集中在：

顺序表：
双指针
归并
排序
二分查找

链表：
头插
尾插
逆置
归并
双指针

三十四、顺序表高频套路 1：双指针删除

例如：

删除顺序表中所有值为 $x$ 的元素。

最笨办法：

发现一个：

后面全部前移

假设很多元素都等于 $x$ ，可能变成：

O (n^{2})

更优方法

两个指针：

i：扫描原数组
k：记录保留元素应放的位置

例如：

1 2 3 2 4 2 5

删 2。

扫描：

1 → 保留
3 → 保留
4 → 保留
5 → 保留

逐个写回：

1 3 4 5

代码思想：

int k = 0;

for (int i = 0; i < L.length; i++) {
    if (L.data[i] != x)
        L.data[k++] = L.data[i];
}

L.length = k;

复杂度：

T (n) = O (n)

S (n) = O (1)

核心思想：

不要每删一个就整体移动，而是一次扫描完成压缩。

三十五、顺序表高频套路 2：有序表去重

例如：

1 1 2 2 2 4 5 5

结果：

1 2 4 5

因为有序，相同元素必然连续。

设：

i：最后一个保留元素
j：扫描指针

若：

A[j] != A[i]

说明发现新值：

A[++i] = A[j];

最终长度：

i + 1

时间：

O (n)

空间：

O (1)

三十六、高频套路 3：两个有序表归并

例如：

A: 1 3 6 9
B: 2 4 5 8

设置：

i 指向 A
j 指向 B

比较：

A[i] < B[j]

谁小拿谁。

过程：

如果长度分别为：

m, n

则：

T (m, n) = O (m + n)

这就是后续归并排序等算法的基础。

三十七、链表高频套路：双指针

资料的复习总结也把双指针、快慢指针列为本章重要算法技巧。

1. 找倒数第 $k$ 个结点

例如：

1 → 2 → 3 → 4 → 5

找倒数第 2 个：

设置：

fast
slow

先让：

fast

领先 $k$ 个结点。

然后一起移动：

slow → ...
fast → ...

当：

fast

到尾时：

slow

正好在倒数第 $k$ 个。

复杂度：

O (n)

空间：

O (1)

2. 找链表中点

slow 每次走1步
fast 每次走2步

例如：

1 → 2 → 3 → 4 → 5

开始：

slow = 1
fast = 1

第一次：

slow = 2
fast = 3

第二次：

slow = 3
fast = 5

fast 到末尾。

所以：

slow = 中点

3. 判断是否有环

同样：

slow 每次1
fast 每次2

如果有环：

快指针最终一定会追上慢指针。

如果：

fast == slow

则有环。

这一思想后续图、链表综合算法也会不断出现。

三十八、链表高频套路：两个链表的公共结点

假设：

A: 1 → 2 → 7 → 8 → 9
              ↑
B:     4 → 5 ┘

如果是真正共享结点，从第一次公共结点开始，后面必然全部相同。

原因很简单。

对结点 7：

7.next

只有一个值。

不可能：

在 A 中指向8
在 B 中又指向另一个节点

一种典型方法：

求 A 长度 $m$ ；
求 B 长度 $n$ ；
长链先走：

∣ m - n ∣

步； 4. 然后一起移动； 5. 第一次：

p == q

的位置就是公共结点。

复杂度：

O (m + n)

三十九、算法题如何写才能拿分？

资料明确提醒：408 算法题并不要求你写工业级、完全可运行的程序，核心是算法思想与关键代码。

推荐固定格式。

第一步：写算法思想

例如逆置：

设置三个指针 pre、p、r。pre 指向已逆置部分，p 指向当前待处理结点，r 暂存 p 的后继。逐个修改当前结点的 next 指向前驱，直至链表结束。

第二步：代码

while (p != NULL) {
    r = p->next;
    p->next = pre;
    pre = p;
    p = r;
}

第三步：复杂度

每个结点访问一次：

T (n) = O (n)

仅使用若干指针：

S (n) = O (1)

这样写非常清晰。

四十、本章几个经典选择题陷阱

题库里第 2 章的选择题重点也非常集中。

陷阱 1：头插语句顺序

正确：

p->next = L->next;
L->next = p;

不能倒。

陷阱 2：静态链表后继

若：

是当前结点数组下标。

后继下标：

S[i].link

后继数据：

S[S[i].link].data

陷阱 3：双链表修改旧指针过早

例如前插：

x->next = p;
x->prev = p->prev;
p->prev->next = x;
p->prev = x;

如果过早：

p->prev = x;

后面：

p->prev

已经不再表示原前驱。

四十一、本章复杂度总表——考前必须能秒答

操作	顺序表	单链表
按位访问	$O (1)$	$O (n)$
无序按值查找	$O (n)$	$O (n)$
表头插入	$O (n)$	$O (1)$
表尾插入	$O (1)$ （容量足够）	有尾指针 $O (1)$ ，否则 $O (n)$
已知前驱后插	不适用类似优势	$O (1)$
删除首元素	$O (n)$	$O (1)$
删除尾元素	$O (1)$	普通单链表 $O (n)$
已知非尾结点删除	顺序表仍需移动	可用复制后继技巧 $O (1)$