Appearance
408
数据结构
DS-02-03 线性表的链式存储（单链表/双链表/循环链表）
一、定位信息
| 项目 | 内容 |
|---|---|
| 所属圈层 | 核心层 |
| 考点热度 | H级（高频重点） — 链表是408数据结构的核心考点，近5年大题几乎每年都有链表算法设计题，分值6–12分 |
| 前置知识回顾 | 需掌握线性表ADT（DS-02-01）、顺序表操作（DS-02-02）、指针与动态内存分配的基本概念 |
| 知识网络定位 | 链式存储是线性表的第二种物理实现，与顺序存储互补。单链表是栈/队列链式实现的基础，双链表是操作系统内存管理的基础 |
二、知识点讲解
2.1 链式存储的基本思想
链式存储不要求元素在内存中连续存放，而是通过指针将分散的存储单元串联起来，形成一条"链"。
每个结点分为两部分：
- 数据域：存储数据元素
- 指针域：存储下一个结点的地址
直观理解：链表就像寻宝游戏——每个宝箱里有宝物（数据）和一张纸条，纸条写着下一个宝箱的位置。你只能按纸条的指引一个一个找，不能直接跳到第 个宝箱。
2.2 单链表（Singly Linked List）
存储结构定义
c
typedef struct LNode { // 单链表结点类型
ElemType data; // 数据域
struct LNode *next; // 指针域，指向下一个结点
} LNode, *LinkList; // LNode是结点类型，LinkList是指向结点的指针类型关键概念：
- 头指针：指向链表第一个结点的指针，是链表的"入口"
- 头结点：在第一个数据结点之前附加的一个结点（数据域可空），头结点不计入表长
- 带头结点 vs 不带头结点：408考试中通常默认带头结点，因为带头结点可以统一处理空表和非空表的操作
【图示说明】带头结点的单链表：HEAD → [头结点] → [a₁] → [a₂] → ... → [aₙ] → NULL
- HEAD 指向头结点
- 头结点的 next 指向第一个数据结点 a₁
- 最后一个结点 aₙ 的 next 指向 NULL
基本操作
（1）初始化 InitList
c
// 初始化一个带头结点的空单链表
bool InitList(LinkList &L) {
L = (LNode *)malloc(sizeof(LNode)); // ① 创建头结点
if (L == NULL) // ② 内存分配失败
return false;
L->next = NULL; // ③ 头结点的next置空
return true;
}时间复杂度：
（2）头插法建表（重要！）
c
// 头插法：将数组a的n个元素逆序建立单链表
LinkList CreateList_Head(int a[], int n) {
LinkList L;
InitList(L); // ① 初始化头结点
for (int i = 0; i < n; i++) { // ② 逐个插入
LNode *s = (LNode *)malloc(sizeof(LNode)); // ③ 创建新结点
s->data = a[i]; // ④ 赋值
s->next = L->next; // ⑤ 新结点指向原第一个结点
L->next = s; // ⑥ 头结点指向新结点
}
return L;
}- 特点：插入顺序与输入顺序相反（逆序建表）
- 时间复杂度：
（3）尾插法建表（重要！）
c
// 尾插法：将数组a的n个元素顺序建立单链表
LinkList CreateList_Tail(int a[], int n) {
LinkList L;
InitList(L); // ① 初始化头结点
LNode *r = L; // ② r指向尾结点（初始为头结点）
for (int i = 0; i < n; i++) { // ③ 逐个插入
LNode *s = (LNode *)malloc(sizeof(LNode)); // ④ 创建新结点
s->data = a[i]; // ⑤ 赋值
r->next = s; // ⑥ 尾结点指向新结点
r = s; // ⑦ 更新尾指针
}
r->next = NULL; // ⑧ 尾结点的next置空
return L;
}- 特点：插入顺序与输入顺序相同（顺序建表）
- 时间复杂度：
（4）按位查找 GetElem
c
// 查找第i个位置的结点（带头结点），返回结点指针
LNode *GetElem(LinkList L, int i) {
if (i < 0) // ① i<0不合法
return NULL;
LNode *p = L; // ② p从头结点开始
int j = 0; // ③ j记录当前位序（头结点位序为0）
while (p != NULL && j < i) { // ④ 循环找第i个结点
p = p->next; // ⑤ p后移
j++; // ⑥ 位序加1
}
return p; // ⑦ 返回第i个结点的指针（或NULL）
}- 时间复杂度：（最坏需遍历整个链表）
- 注意：
i=0时返回头结点，i=1时返回第一个数据结点
（5）插入操作 ListInsert（后插操作）
c
// 在第i个位置插入元素e（带头结点）
bool ListInsert(LinkList &L, int i, ElemType e) {
LNode *p = GetElem(L, i - 1); // ① 找到第i-1个结点（前驱）
if (p == NULL) // ② 前驱不存在，插入位置不合法
return false;
LNode *s = (LNode *)malloc(sizeof(LNode)); // ③ 创建新结点
s->data = e; // ④ 赋值
s->next = p->next; // ⑤ 新结点指向原第i个结点
p->next = s; // ⑥ 前驱指向新结点
return true;
}- 时间复杂度：（主要耗时在查找前驱结点）
- 核心操作只有两步（⑤和⑥），顺序不能颠倒！
（6）删除操作 ListDelete
c
// 删除第i个位置的元素，用e返回（带头结点）
bool ListDelete(LinkList &L, int i, ElemType &e) {
LNode *p = GetElem(L, i - 1); // ① 找到第i-1个结点（前驱）
if (p == NULL || p->next == NULL) // ② 前驱不存在或第i个结点不存在
return false;
LNode *q = p->next; // ③ q指向要删除的结点
e = q->data; // ④ 保存被删元素的值
p->next = q->next; // ⑤ 前驱指向后继
free(q); // ⑥ 释放被删结点
return true;
}- 时间复杂度：
2.3 双链表（Doubly Linked List）
存储结构定义
c
typedef struct DNode { // 双链表结点类型
ElemType data; // 数据域
struct DNode *prior; // 前驱指针
struct DNode *next; // 后继指针
} DNode, *DLinkList;优势：可以双向遍历，删除给定结点时无需查找前驱（）。
插入操作（在结点p之后插入结点s）
c
// 在双链表的结点p之后插入结点s（4步，顺序可调整但需保证不丢失指针）
s->next = p->next; // ① s的后继指向p的后继
p->next->prior = s; // ② p的后继的前驱指向s（前提：p->next != NULL）
s->prior = p; // ③ s的前驱指向p
p->next = s; // ④ p的后继指向s时间复杂度：（已知结点p的情况下）
删除操作（删除结点p之后的结点q）
c
// 删除双链表中结点p的后继结点q
q = p->next; // ① q指向要删除的结点
p->next = q->next; // ② p的后继指向q的后继
if (q->next != NULL) // ③ 若q不是最后一个结点
q->next->prior = p; // ④ q的后继的前驱指向p
free(q); // ⑤ 释放q时间复杂度：
2.4 循环链表（Circular Linked List）
循环单链表：最后一个结点的 next 不指向 NULL，而是指向头结点（或第一个结点）。
循环双链表：头结点的 prior 指向尾结点，尾结点的 next 指向头结点。
判断空表：
- 循环单链表（带头结点）：
L->next == L - 循环双链表（带头结点）：
L->next == L && L->prior == L
优势：从任意结点出发可以遍历整个链表；在尾部操作时若已知尾结点，可以 完成。
2.5 三种链表综合对比
| 对比项 | 单链表 | 双链表 | 循环链表 |
|---|---|---|---|
| 指针域 | 1个（next） | 2个（prior, next） | 1或2个 |
| 空间开销 | 最小 | 最大（每个结点多一个指针） | 同单/双链表 |
| 删除已知结点p | 需找前驱 | 不需找前驱 | 同单/双链表 |
| 双向遍历 | ❌ | ✅ | 取决于单/双 |
| 判空条件 | L->next == NULL | 双重判断 | L->next == L |
| 适用场景 | 一般场景 | 需要频繁双向遍历 | 约瑟夫环等环形问题 |
三、记忆与理解辅助
技巧1：头插法 vs 尾插法口诀
"头插逆序尾插顺，头插简单尾要针"
- 头插法：结果与输入逆序，实现简单（只需头指针）
- 尾插法：结果与输入顺序，需要额外的尾指针
r
技巧2：单链表插入/删除的"绑线"口诀
"先绑新线再断旧，顺序反了就断链"
插入时：
- 先让新结点
s接上后面的结点（s->next = p->next） - 再让前驱
p指向新结点（p->next = s）
如果顺序反了，p->next 的原值就丢失了！
技巧3：双链表插入的4步记忆法
"先连后继再连前，两前两后四步全"
s->next = p->next; // 连后：s连上p的后继
p->next->prior = s; // 反连：p的后继连回s
s->prior = p; // 连前：s连上p
p->next = s; // 反连：p连上s技巧4：链表类型选择速查表
| 需求 | 推荐类型 |
|---|---|
| 只需单向遍历 | 单链表 |
| 需要频繁双向遍历 | 双链表 |
| 删除已知结点（不给前驱） | 双链表（） |
| 环形结构（约瑟夫环等） | 循环链表 |
| 内存紧张 | 单链表（指针域最少） |
四、例题与精解
例题1（基础）
命题意图：考查单链表头插法和尾插法的区别。
题目：依次将数据 (1, 2, 3, 4, 5) 插入带头结点的空单链表中。分别写出用头插法和尾插法建立的链表的数据序列。
审题分析：
- 输入序列：1, 2, 3, 4, 5
- 需要分别用头插法和尾插法模拟建表过程
解题思路：头插法每次插在头结点之后（最前面），尾插法每次插在最后面。
完整步骤：
头插法过程：
| 步骤 | 插入元素 | 链表状态（头结点后的数据序列） |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 2 | 2 → 1 |
| 3 | 3 | 3 → 2 → 1 |
| 4 | 4 | 4 → 3 → 2 → 1 |
| 5 | 5 | 5 → 4 → 3 → 2 → 1 |
尾插法过程：
| 步骤 | 插入元素 | 链表状态（头结点后的数据序列） |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 2 | 1 → 2 |
| 3 | 3 | 1 → 2 → 3 |
| 4 | 4 | 1 → 2 → 3 → 4 |
| 5 | 5 | 1 → 2 → 3 → 4 → 5 |
结果：
- 头插法：
5 → 4 → 3 → 2 → 1（逆序） - 尾插法：
1 → 2 → 3 → 4 → 5（顺序）
方法反思：在408算法大题中，若要求"按输入顺序建立链表"，必须用尾插法；若要求"逆序"，用头插法更简洁。审题时务必注意这一点。
例题2（中等）
命题意图：考查单链表的算法设计能力（就地逆置）。
题目：设计一个算法，将带头结点的单链表就地逆置（即不额外申请新结点），要求时间复杂度 ，空间复杂度 。
审题分析：
- 输入：带头结点的单链表
- 输出：逆置后的 （原地修改）
- 约束：不能新建结点，只能修改指针
解题思路：用头插法逆置思想——依次摘下每个数据结点，用头插法重新插入到头结点之后。这样原来在后面的结点会被插到前面，实现逆置。
完整步骤：
c
// 将带头结点的单链表就地逆置
void ReverseList(LinkList &L) {
LNode *p = L->next; // ① p指向第一个数据结点
L->next = NULL; // ② 断开头结点与后续结点的连接
while (p != NULL) { // ③ 遍历原链表的每个结点
LNode *q = p->next; // ④ 保存p的后继（因为马上要修改p->next）
p->next = L->next; // ⑤ 头插法步骤1：p指向原第一个结点
L->next = p; // ⑥ 头插法步骤2：头结点指向p
p = q; // ⑦ p移动到下一个待处理结点
}
}图示过程（以 为例）：
| 步骤 | p | 链表状态（头结点后） | 说明 |
|---|---|---|---|
| 初始 | 1 | 1 → 2 → 3 | p指向1 |
| ② | 1 | 空 | 断开头结点 |
| 第1轮⑤⑥ | 2 | 1 | 将1头插 |
| 第2轮⑤⑥ | 3 | 2 → 1 | 将2头插 |
| 第3轮⑤⑥ | NULL | 3 → 2 → 1 | 将3头插 |
结果： ✅
复杂度分析：
- 时间：每个结点访问一次， ✅
- 空间：只用常数个指针变量， ✅
方法反思：
- 核心思想：头插法天然产生逆序，利用这个特性实现逆置
- 步骤④保存后继是关键，不保存的话步骤⑤会丢失后续结点
- 变式：可以用"三指针法"（pre, cur, next）从前往后逐个反转指针方向，效果相同
五、考情分析
| 分析维度 | 说明 |
|---|---|
| 考查频次 | 近5年每年必考，是408数据结构出题最密集的知识点之一 |
| 常见题型 | 选择题（链表操作分析、头插法/尾插法辨析）；大题（链表算法设计，如逆置、合并、查找倒数第k个等） |
| 分值占比 | 约6–12分（大题8分居多，选择题2分） |
| 命题趋势 | 链表大题难度稳定在中等偏上，常结合双指针、递归等技巧；近年出现过"链表+排序"、"链表+环检测"等综合题 |
六、易错点提醒
易错点1
- 错误表现：单链表插入/删除时，先修改
p->next再保存原值 - 错误原因：没有意识到修改
p->next会丢失原链表信息 - 正确做法：插入时先
s->next = p->next（先让新结点接上后面），再p->next = s。删除时先q = p->next保存要删的结点，再p->next = q->next
易错点2
- 错误表现：混淆"带头结点"和"不带头结点"的链表操作差异
- 错误原因：头结点的存在使得所有操作（包括第一个结点的操作）都可以统一处理
- 正确做法：408考试中默认带头结点。带头结点时， 永远不为NULL（空表时 ）；不带头结点时，空表
易错点3
- 错误表现：双链表插入时遗漏某一步指针修改，导致链表断裂或指针悬空
- 错误原因：双链表有4步操作，容易漏掉某一步
- 正确做法：牢记"两前两后"——每个方向的连接都要做两次（
s连p，p连s），共4步
易错点4
- 错误表现：尾插法建表后忘记将尾结点的
next置为NULL - 错误原因：
malloc分配的内存内容不确定，不置空可能导致野指针 - 正确做法：尾插法最后必须
r->next = NULL，头插法因为是从头结点的next开始，头结点初始化时已置NULL，所以不用额外处理
易错点5
- 错误表现：在链表算法中不考虑空表或只有一个结点的边界情况
- 错误原因：只关注一般情况，忽略特殊情况
- 正确做法：算法题中务必检查：空表（）、单结点表、头结点/尾结点等边界情况
七、来源标注
- 依据2026考研统考大纲——数据结构部分"线性表的链式存储"
- 依据《数据结构（C语言版）》严蔚敏版第二章
- 依据《数据结构》王道考研辅导讲义