【王道考研·数据结构】第二章线性表（整合版）

Austoin2026-03-262026-03-27

引言

第二章的主题是线性表。这一章虽然从名字上看很简单，但它实际上承担了两个非常重要的任务：

让你第一次系统理解“逻辑结构”和“存储结构”的区别
让你第一次真正面对“增删查改不同实现方式带来的效率差异”
线性表这一章最重要的不是背定义，而是建立下面这个整体框架：

线性表是什么
顺序表怎么实现
链表怎么实现
它们各自适合什么场景
本篇基于现有旧文章内容，把第二章的线性表、顺序表、链表体系合并成一篇完整复习文章。

图像化理解（Mermaid）

  mindmap
  root((第二章核心地图))
    线性表（逻辑结构）
      顺序表（连续存储）
        按位查找 O(1)
        插删搬移 O(n)
      链表（离散存储+指针连接）
        单链表
        双链表
        循环链表
        静态链表

一句话理解：第二章在比较“同一逻辑结构的两种实现代价”。

一、线性表的定义与基本操作

1. 线性表的定义

线性表（Linear List）是具有相同数据类型的 n (n >= 0) 个数据元素的有限序列。
当 n = 0 时，称为空表。
通常记作：

1	L = (a1, a2, ..., ai, ai+1, ..., an)

2. 线性表的三个核心特性

（1）有限性

元素个数必须有限。

（2）同类型

所有元素的数据类型必须相同，因此每个元素所占空间大小也一样。

（3）有序性

元素之间存在先后次序。
也正因为这种“一对一”的线性关系，线性表才和树、图这些更复杂结构区别开来。

3. 线性表的重要术语

表长：线性表中元素的个数 n
表头元素：a1
表尾元素：an
前驱：除表头元素外，每个元素有且仅有一个直接前驱
后继：除表尾元素外，每个元素有且仅有一个直接后继

4. 位序与数组下标的区别

这是整个第二章最基础、也最容易错的地方。

线性表讨论的是位序，从 1 开始
C / C++ 数组讨论的是下标，从 0 开始
例如：
第 i 个元素的位序是 i
它在数组中的位置通常是 data[i - 1]
后面写顺序表、链表插入删除代码时，这个区分必须始终清楚。

5. 线性表的基本操作

最常用的操作可以概括为：

创、销、增、删、查

（1）创与销

InitList(&L)：初始化一个空表
DestroyList(&L)：销毁线性表，释放其占用空间

（2）增与删

ListInsert(&L, i, e)：在第 i 个位序插入元素 e
ListDelete(&L, i, &e)：删除第 i 个位序的元素，并用 e 返回被删值

（3）查找

LocateElem(L, e)：按值查找
GetElem(L, i)：按位查找

（4）其他常见操作

Length(L)：求表长
PrintList(L)：输出表中元素
Empty(L)：判空

6. 为什么很多函数参数要带 `&`

旧文里专门讲了引用传参，这对理解数据结构代码非常重要。
核心原则只有一句：

如果修改结果要“带回来”，就需要传引用。
例如：

插入、删除会改变线性表本身，所以需要 &L
删除时要把被删元素带出来，所以 e 也常写成引用参数
按位查找只读取数据，不修改表，因此通常不需要 &L

7. 封装基本操作的意义

封装线性表的基本操作，不只是为了写代码好看，它还有几个实际意义：

统一接口，便于团队协作
降低重复劳动
在考研大题中能直接调用标准操作思维，避免代码散乱

二、顺序表

1. 顺序表的定义

顺序表是用顺序存储方式实现的线性表。
它的核心思想是：

逻辑上相邻的元素，在物理存储位置上也相邻。
这也是顺序表和链表最根本的区别。

2. 顺序表的优缺点

优点

随机访问：可以在 O(1) 时间内找到第 i 个元素
存储密度高：每个存储单元只存数据本身，不额外存指针

缺点

扩容不方便
插入、删除时可能需要移动大量元素

3. 顺序表的静态分配

静态分配通常用固定大小数组实现：

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

特点：

容量固定
空间一旦用满，就无法继续插入

4. 顺序表的动态分配

动态分配通常写成：

#define InitSize 10
typedef struct {
    ElemType *data;
    int MaxSize;
    int length;
} SeqList;

虽然叫“动态分配”，但它本质上仍然是顺序表，因为：

内存依然必须是一整片连续空间
只是这片连续空间由 malloc 动态申请

5. 动态扩容的本质

这是顺序表非常常考的一个理解点。
扩容不是“在原数组后面直接补一段空间”，而是：

重新申请一块更大的连续空间
把旧数据复制过去
释放旧空间
因此：
如果申请扩大 m 个位置失败，并不是说明系统没有 m 个连续空间，而是说明找不到 n + m 个连续空间。

6. 顺序表的插入操作

目标：在顺序表第 i 个位序插入新元素 e。
核心思路：

把第 i 个及之后的元素全部向后移动一位
再把 e 放到第 i 个位置
代码框架：

bool ListInsert(SqList &L, int i, ElemType e) {
    if(i < 1 || i > L.length + 1) return false;
    if(L.length >= MaxSize) return false;
    for(int j = L.length; j >= i; j--) {
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e;
    L.length++;
    return true;
}

必须记住：

插入时元素要从后往前移动。
否则数据会被覆盖。

时间复杂度

最好：O(1)（插在表尾）
最坏：O(n)（插在表头）
平均：O(n)

7. 顺序表的删除操作

目标：删除第 i 个位序元素，并用 e 返回被删值。
核心思路：

先保存第 i 个元素
把其后的所有元素向前移动一位进行覆盖
代码框架：

bool ListDelete(SqList &L, int i, ElemType &e) {
    if(i < 1 || i > L.length) return false;
    e = L.data[i - 1];
    for(int j = i; j < L.length; j++) {
        L.data[j - 1] = L.data[j];
    }
    L.length--;
    return true;
}

必须记住：

删除时元素要从前往后移动。

时间复杂度

最好：O(1)（删表尾）
最坏：O(n)（删表头）
平均：O(n)

8. 顺序表的查找操作

（1）按位查找 `GetElem(L, i)`

本质是直接访问数组：

1	data[i - 1]

所以时间复杂度是：

O(1)

这就是顺序表“随机存取”特性的来源。

（2）按值查找 `LocateElem(L, e)`

需要从头到尾依次比较，所以复杂度是：

O(n)

9. 顺序表与数组的区别

这是考研很喜欢考的概念题。

数组：存储结构 / 语言层面的数据容器
顺序表：线性表这种逻辑结构的一种实现方式
顺序表通常要比“纯数组”多出：
表长 length
最大容量 MaxSize
插入、删除、查找等操作语义
所以顺序表不是“一维数组”的同义词。

三、链表总览

顺序表的主要缺点是：

要求连续空间
插入、删除时要移动大量元素
为了解决这些问题，链表应运而生。
链表的本质思想是：
逻辑上相邻的元素，不要求物理位置相邻，而是通过指针把它们串起来。

四、单链表

1. 单链表的定义

单链表的每个结点包含：

数据域 data
指针域 next
结构定义：

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

2. 带头结点与不带头结点

不带头结点

第一个数据结点本身就是表头
插入删除时经常要单独讨论第一个结点
代码容易出现很多额外判断

带头结点

头结点不存放实际数据
只是为了统一插入删除逻辑
考研中通常默认推荐这种写法
初始化代码：

bool InitList(LinkList &L) {
    L = (LNode *)malloc(sizeof(LNode));
    if (L == NULL) return false;
    L->next = NULL;
    return true;
}

判空条件：

1	L->next == NULL

3. 单链表的插入操作

（1）按位序插入

思想：先找到第 i - 1 个结点，再插入到它后面。

（2）指定结点后插

这是最基本的链表插入动作：

bool InsertNextNode(LNode *p, ElemType e) {
    if (p == NULL) return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) return false;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

这里的关键是：

先让新结点连上后继，再让前驱连上新结点。
否则会断链。
时间复杂度：

O(1)

（3）指定结点前插（偷天换日法）

如果只知道结点 p，但不知道其前驱，怎么在 p 前插入？
做法：

把新结点 s 插到 p 的后面
交换 p 与 s 的数据域
这样逻辑上看起来就像是在 p 前插入了新元素。
这是一类非常经典的考研技巧。

4. 单链表的删除操作

（1）按位序删除

先找到第 i - 1 个结点，再把第 i 个结点绕过去，并释放其空间。

（2）删除指定结点 `p`

若不知道前驱，可用“偷天换日法 2.0”：

把后继结点的数据复制到 p
删除 p 的后继结点

LNode *q = p->next;
p->data = q->data;
p->next = q->next;
free(q);

但要注意边界：

如果 p 是最后一个结点，这种方法失效。

5. 单链表的建立

（1）尾插法

设置尾指针 r 指向当前表尾，新结点始终接在 r 后面。
特点：

生成链表顺序与输入顺序一致

（2）头插法

新结点始终插到头结点之后。
特点：

生成链表顺序与输入顺序相反
本质上可用于链表逆置
这也是后面很多链表题的核心技巧。

五、双链表

双链表在单链表基础上增加了一个前驱指针 prior。
结构定义：

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

1. 双链表的优势

能更方便地逆向检索
删除和插入时更容易处理前驱关系

2. 插入时的指针修改顺序

在 p 后插入 s：

s->next = p->next;
if (p->next != NULL) p->next->prior = s;
s->prior = p;
p->next = s;

修改顺序必须谨慎，否则会断链。

3. 删除操作

删除 p 的后继 q：

1
2
3

p->next = q->next;
if (q->next != NULL) q->next->prior = p;
free(q);

六、循环链表

1. 循环单链表

循环单链表中，表尾结点的 next 不再是 NULL，而是指向头结点。

判空条件

1	L->next == L

特点

从任意结点出发都能走遍整个表
常常可以只保留尾指针 R
R->next 就是头结点

2. 循环双链表

表头结点的 prior 指向表尾
表尾结点的 next 指向表头

判空条件

1	L->next == L && L->prior == L

七、静态链表

静态链表本质上是：

用数组来模拟链表。
结构定义：

#define MaxSize 10
typedef struct {
    ElemType data;
    int next;
} SLinkList[MaxSize];

其中：

next 不再是真正指针，而是“下一个结点的数组下标”
0 号位置常常充当头结点
next == -1 常表示到达表尾

1. 优点

插入删除不需要大规模移动元素
不依赖真实指针

2. 适用场景

不支持指针的语言环境
某些底层系统实现，如 FAT 文件分配表

八、顺序表 vs 链表

这是第二章最常见的综合对比题。

1. 相同点

都属于线性结构
都可以实现线性表

2. 不同点

（1）存储结构不同

顺序表：连续存储
链表：离散存储

（2）查找效率不同

顺序表按位查找：O(1)
链表按位查找：O(n)

（3）插入删除效率不同

顺序表：移动元素，平均 O(n)
链表：找到位置后改指针，局部操作可 O(1)

（4）空间特点不同

顺序表：存储密度高，但扩容和连续空间是问题
链表：空间分配灵活，但每个结点额外需要指针空间

3. 如何选择

适合顺序表的场景

表长较稳定
经常按位访问第 i 个元素
尾部插入删除较多

适合链表的场景

表长难以预估
经常进行插入、删除
不要求高频随机访问
一句话总结：
查得多，用顺序表；改得多，用链表。

九、基于旧文内容整理的经典链表题型

第 34 篇旧文后半部分整理了不少链表大题，这里把题型思路统一收拢。

1. 找倒数第 k 个结点

核心思路：快慢双指针

快指针先走 k 步
然后快慢同步走
快指针到尾时，慢指针刚好指向倒数第 k 个结点

2. 找两个链表的共同后缀起始位置

核心思路：长度对齐

先分别求两表长度
让长链表先走长度差
然后两个指针同步向后
第一个地址相同的结点就是交点
注意：
比较的是结点地址，不是数据值。

3. 删除绝对值相等的后续结点

核心思路：哈希数组 / 空间换时间

若已知绝对值范围有限
就用数组记录某个绝对值是否出现过
后续重复结点直接删除

4. 重排链表 `a1, an, a2, a(n-1)...`

核心思路：

快慢指针找中点
逆置后半段
两段交替合并
这是链表综合题中的经典大题，几乎融合了：

找中点
逆置链表
交替合并
三个高频技巧。

十、图像化总览（Mermaid）

1. 位序与下标关系图

  flowchart TD
    A[位序 i] --> B[data[i-1]]
    C[位序从 1 开始] --> A
    D[数组下标从 0 开始] --> B

2. 顺序表插删搬移方向图

  flowchart TD
    I0[插入第 i 位]
    I1[从后往前搬移 ai..an]
    I2[在 i 位放入 e]
    I0 --> I1 --> I2
    D0[删除第 i 位]
    D1[先保存 ai]
    D2[从前往后搬移 ai+1..an]
    D0 --> D1 --> D2

3. 单链表前插“偷天换日”图

  flowchart LR
    A[仅知道结点 p] --> B[先后插新结点 s]
    B --> C[交换 p.data 与 s.data]
    C --> D[逻辑效果: 在 p 前插入 x]

4. 四类链表关系图

  mindmap
  root((链表家族))
    单链表（next）
    双链表（prior+next）
    循环单链表（尾.next->头）
    循环双链表（头.prior->尾, 尾.next->头）

十一、易错点与易混淆点（详细版）

A. 易混淆点（A vs B）

线性表 vs 顺序表
- 线性表：逻辑结构（有序序列）
- 顺序表：线性表的一种存储实现（连续空间）
- 不能把顺序表等同于“线性表本体”。
顺序表 vs 数组
- 数组是语言容器；顺序表是“数组 + length + 操作语义”。
- 只给数组，不等于完成了顺序表 ADT。
链式存储“离散” vs 逻辑“连续”
- 逻辑上相邻靠指针维持，不靠物理地址连续。
- 这句话是链表本质，高频选择题陷阱。
静态链表 vs 顺序表
- 静态链表虽然用数组，但 next 存的是“下一个下标”，本质仍是链式逻辑。

B. 易错点（为什么错 + 怎么改）

位序/下标混用导致越界
- 错因：把第 i 位直接写成 data[i]。
- 正解：顺序表第 i 位是 data[i-1]。
顺序表插入搬移方向写反
- 错因：从前往后搬移会覆盖原值。
- 正解：插入必须从后往前搬。
顺序表删除搬移方向写反
- 错因：从后往前搬会留下空洞。
- 正解：删除必须从前往后搬覆盖。
“动态顺序表”误以为不需要连续内存
- 错因：把“动态申请”理解成“分散存储”。
- 正解：动态顺序表依然要求一整段连续空间。
单链表删除指定结点漏判尾结点
- 错因：无脑套“复制后继再删后继”。
- 正解：该法仅当 p->next != NULL 才成立；删尾结点必须找到前驱。
双链表指针修改顺序错
- 错因：先断开主链再回填，导致断链。
- 正解：先连新结点到两侧，再改两侧指向新结点。

C. 顺序表与链表选型速查

如果：查第 i 个元素特别频繁 -> 选顺序表
如果：中间插删特别频繁      -> 选链表
如果：长度难预估            -> 倾向链表
如果：内存紧凑优先          -> 倾向顺序表

十二、书签级思维导图复现（第二章，Mermaid）

  mindmap
  root((第2章 线性表))
    2.1 线性表定义与基本操作
      线性表定义（同类型、有限、有序）
      位序与下标映射
      创销增删查
      ADT 接口与实现分离
    2.2 顺序表
      顺序存储定义
      静态分配/动态分配
      插入（后移）/删除（前移）
      按位查找 O(1) / 按值查找 O(n)
      扩容本质（重新申请+复制）
    2.3 链式存储
      单链表（带头结点）
      双链表（prior+next）
      循环链表（尾连头）
      静态链表（数组模拟指针）
      顺序表与链表适用场景对比

十三、PDF 例题与知识点补充（线性表）

例题 1：位序与下标换算

题目：顺序表中第 i 个元素在数组中的下标是多少？

答案：i - 1。

详细解析：

线性表位序从 1 开始，数组下标从 0 开始。
两者固定相差 1，所以第 i 位对应 data[i-1]。

例题 2：顺序表插入最坏移动次数

题目：长度为 n 的顺序表，在第 1 位插入元素，最少/最多移动多少个元素？

答案：

最少 0（插在尾部）
最多 n（插在第 1 位）

详细解析：

插入需要先腾出目标位置。
插在尾部无需搬移，代价最小。
插在第 1 位要把原有 n 个元素整体后移，代价最大。

例题 3：顺序表删除复杂度

题目：删除第 i 位元素的平均时间复杂度？

答案：O(n)。

详细解析：

删除后必须把后续元素前移覆盖空洞。
平均移动次数与 n 同阶，数量级不变。
因此平均复杂度是 O(n)。

例题 4：动态顺序表扩容判断

题目：原数组剩余空间零散，只要总剩余空间够 m，就一定能扩容成功。判断正误。

答案：错误。

详细解析：

顺序表要求连续存储。
零散空间不能直接拼成连续块。
扩容本质是申请新的连续区，再复制旧数据。

例题 5：单链表前插（无前驱）

题目：仅给定结点 p，如何在 p 前插入新元素 x？

答案：后插新结点 s，再交换 p.data 与 s.data。

详细解析：

无前驱时不能直接改前驱 next。
先把 s 插到 p 后，结构上可行。
交换数据后，逻辑效果等价于“在 p 前插入”。

例题 6：单链表删除指定结点

题目：仅给定结点 p 指针，如何 O(1) 删除？

答案：复制 p->next 的数据到 p，再删除 p->next。

详细解析：

常规删除要前驱，本题拿不到前驱。
用后继覆盖当前结点可绕开前驱需求。
该法仅在 p 非尾结点时成立。

例题 7：头插法建表后顺序

题目：依次输入 1,2,3,4，用头插法建单链表，最终序列？

答案：4,3,2,1。

详细解析：

每个新结点都插到头结点之后。
后输入元素会排在前面，序列整体逆转。

例题 8：尾插法建表后顺序

题目：依次输入 1,2,3,4，用尾插法建单链表，最终序列？

答案：1,2,3,4。

详细解析：

尾插每次都接在末尾。
相对次序保持不变，因此与输入一致。

例题 9：双链表删除指针修改

题目：删除 q（q 在 p 后）时关键指针修改是什么？

答案：

1
2
3

p->next = q->next;
if (q->next != NULL) q->next->prior = p;
free(q);

详细解析：

先让 p->next 越过 q。
若 q 有后继，还要回连后继的 prior。
最后释放 q，避免内存泄漏。

例题 10：循环单链表判空

题目：带头结点循环单链表如何判空？

答案：L->next == L。

详细解析：

空表时头结点后继指向自己。
非空时头结点后继应为首元结点。

例题 11：静态链表定位

题目：静态链表中 next 字段表示什么？

答案：表示下一个结点在数组中的下标，不是真实地址。

详细解析：

静态链表是“数组 + 下标链接”的链式模拟。
所以 next 存的是位置编号。

例题 12：顺序表 vs 链表选型

题目：频繁按位访问第 i 个元素，偶尔插删，应选哪种结构？

答案：顺序表。

详细解析：

顺序表按位访问 O(1)。
链表按位访问通常 O(n)。
本场景查多改少，优先顺序表。

例题 13：顺序表 vs 链表选型 II

题目：长度不确定，中间插删频繁，应选哪种结构？

答案：链表。

详细解析：

顺序表中间插删要搬移大量元素。
链表在定位后仅改指针，修改代价低。

例题 14：链表公共后缀交点

题目：两链表有公共后缀时，如何找第一个公共结点？

答案：长度对齐后同步后移，首个地址相同结点即交点。

详细解析：

先求两链表长度差 d。
长链表先走 d 步，使两指针到尾部距离一致。
同步移动，第一次地址相同就是交点。

例题 15：倒数第 k 个结点

题目：单链表如何找倒数第 k 个结点？

答案：快慢指针，快指针先走 k 步，再同步走。

详细解析：

快指针领先 k 步后，与慢指针保持固定间距。
快指针到表尾时，慢指针恰在倒数第 k 个。
若快指针不足 k 步即为空，k 非法。

十四、第二章必背核对表

顺序表插入后移方向：从后往前。
顺序表删除前移方向：从前往后。
单链表按位查找：O(n)。
双链表改指针顺序：先连新结点，再连两侧。
循环链表判空条件必须会写。
静态链表本质是链式逻辑。
选型口诀：查得多顺序表，改得多链表。

总结

第二章真正要建立的是一种“实现意识”：

同样是线性表
可以用顺序表实现
也可以用链表实现
但实现方式一变，操作代价就会变
所以这一章不是在背孤立知识点，而是在回答：
同一个逻辑结构，用不同存储结构实现时，性能为什么会不同？
你最后应该真正掌握的内容有：

线性表的定义与基本操作
顺序表的插入、删除、查找与扩容本质
单链表、双链表、循环链表、静态链表的结构与特点
顺序表与链表的优缺点对比
快慢指针、链表逆置、地址对齐、哈希去重这些经典题型套路
只要这些内容吃透，后面第三章的栈和队列、以及再往后的树和图，理解起来都会顺很多。

作者：[Austoin]
参考来源：基于现有旧文章整理

引言

图像化理解（Mermaid）

一句话理解：第二章在比较“同一逻辑结构的两种实现代价”。

一、线性表的定义与基本操作

1. 线性表的定义

2. 线性表的三个核心特性

（1）有限性

（2）同类型

（3）有序性

3. 线性表的重要术语

4. 位序与数组下标的区别

5. 线性表的基本操作

（1）创与销

（2）增与删

（3）查找

（4）其他常见操作

6. 为什么很多函数参数要带 &

7. 封装基本操作的意义

二、顺序表

1. 顺序表的定义

2. 顺序表的优缺点

优点

缺点

3. 顺序表的静态分配

4. 顺序表的动态分配

5. 动态扩容的本质

6. 顺序表的插入操作

时间复杂度

7. 顺序表的删除操作

时间复杂度

8. 顺序表的查找操作

（1）按位查找 GetElem(L, i)

（2）按值查找 LocateElem(L, e)

9. 顺序表与数组的区别

三、链表总览

四、单链表

1. 单链表的定义

2. 带头结点与不带头结点

不带头结点

带头结点

3. 单链表的插入操作

（1）按位序插入

（2）指定结点后插

（3）指定结点前插（偷天换日法）

4. 单链表的删除操作

（1）按位序删除

（2）删除指定结点 p

5. 单链表的建立

（1）尾插法

（2）头插法

五、双链表

1. 双链表的优势

2. 插入时的指针修改顺序

3. 删除操作

六、循环链表

1. 循环单链表

判空条件

特点

2. 循环双链表

判空条件

七、静态链表

1. 优点

2. 适用场景

八、顺序表 vs 链表

1. 相同点

2. 不同点

（1）存储结构不同

（2）查找效率不同

（3）插入删除效率不同

（4）空间特点不同

3. 如何选择

适合顺序表的场景

适合链表的场景

九、基于旧文内容整理的经典链表题型

1. 找倒数第 k 个结点

2. 找两个链表的共同后缀起始位置

3. 删除绝对值相等的后续结点

4. 重排链表 a1, an, a2, a(n-1)...

十、图像化总览（Mermaid）

1. 位序与下标关系图

6. 为什么很多函数参数要带 `&`

（1）按位查找 `GetElem(L, i)`

（2）按值查找 `LocateElem(L, e)`

（2）删除指定结点 `p`

4. 重排链表 `a1, an, a2, a(n-1)...`