链表
含AI生成内容
链表
链式存储的核心特点
链表（Linked List）是线性表的链式存储实现。与顺序表不同，链表的元素在内存中不一定连续存放，通过指针将各个结点链接在一起。
| 核心特点 | 说明 |
|---|---|
| 逻辑顺序 ≠ 物理顺序 | 元素在内存中离散存放，通过指针建立逻辑关系 |
| 顺序访问（Sequential Access） | 只能从头结点出发沿指针链逐个遍历，不支持随机访问 |
| 动态分配 | 按需申请结点空间，不会浪费也不会溢出 |
| 存储密度低 | 每个结点需要额外存储指针域 |
单链表
结点结构
typedef struct LNode { ElemType data; // 数据域 struct LNode *next; // 指针域，指向下一个结点} LNode, *LinkList;存储示意：
头指针 → [data|next] → [data|next] → [data|next] → NULL 结点1 结点2 结点3带头结点 vs 不带头结点
| 对比项 | 带头结点 | 不带头结点 |
|---|---|---|
| 头指针指向 | 头结点（不存数据） | 首元结点（第一个数据结点） |
| 空表条件 | L->next == NULL | L == NULL |
| 在表头插入 | 与其他位置统一 | 需特殊处理（修改头指针） |
| 删除第一个元素 | 与其他位置统一 | 需特殊处理 |
| 408 默认方式 | 是（考场默认） | 仅当题目明确说明时才使用 |
408 考研默认使用带头结点的单链表。头结点让插入/删除操作的代码逻辑统一，不用特判 i=1 的情况。
基本操作
头插法（逆序建表）
每次将新结点插入到头结点之后，建表结果与输入顺序相反。
s->next = L->next;L->next = s;时间复杂度：O(n)。特点：不需要尾指针，代码简洁。
尾插法（正序建表）
每次将新结点插入到链表尾部，建表结果与输入顺序一致。需要维护一个尾指针 r。
r->next = s;r = s;时间复杂度：O(n)。特点：保持输入顺序，但需额外维护尾指针。
插入操作
在第 i 个位置插入时，先找到第 i-1 个结点（前驱结点），然后修改指针。
s->next = p->next; // 步骤 1p->next = s; // 步骤 2易错：以上两步的顺序不能颠倒！如果先执行
p->next = s，就丢失了原第 i 个结点的地址。这是考研选择题的常见陷阱。
删除操作
删除第 i 个位置的元素时，先找到第 i-1 个结点，然后修改指针跳过被删除结点。
q = p->next;p->next = q->next;free(q);逆置操作
将单链表中所有结点的顺序反转，408 考研的高频算法题。
方法一（头插法逆置，推荐）：
void ReverseList(LinkList &L) { LNode *p = L->next, *r; L->next = NULL; while (p != NULL) { r = p->next; p->next = L->next; L->next = p; p = r; }}方法二（指针反转法）：
void ReverseList2(LinkList &L) { LNode *pre = NULL, *p = L->next, *r; while (p != NULL) { r = p->next; p->next = pre; pre = p; p = r; } L->next = pre;}两种方法时空复杂度相同：O(n)、O(1)。头插法思路更直观，考场推荐优先使用。
双链表
结点结构
双链表在单链表的基础上增加了一个 prior 指针，用空间换时间——以额外一个指针域的代价，换来了 O(1) 访问前驱的能力。
typedef struct DNode { ElemType data; struct DNode *prior, *next; // 前驱指针 + 后继指针} DNode, *DLinklist;优势
| 操作 | 单链表 | 双链表 |
|---|---|---|
| 已知结点访问前驱 | O(n) — 需从头遍历 | O(1) — 直接通过 prior |
| 已知结点删除自身 | O(n) — 需先找前驱 | O(1) — prior 直接定位 |
| 在已知结点之前插入 | O(n) — 需先找前驱 | O(1) — prior 直接定位 |
插入操作的指针修改顺序（经典陷阱）
在结点 p 之后插入结点 s，需修改四个指针：
s->next = p->next; // 步骤 1p->next->prior = s; // 步骤 2（若 p 不是尾结点）s->prior = p; // 步骤 3p->next = s; // 步骤 4要点：步骤 1、2 必须在步骤 4 之前完成，否则
p->next会被覆盖，导致原后继结点丢失。循环双链表无需特判是否为尾结点（p->next永不为 NULL）。
删除操作
删除结点 p 的后继结点 q：
p->next = q->next;if (q->next != NULL) q->next->prior = p;free(q);循环链表
循环单链表
尾结点的 next 指向头结点（带头结点时），形成环状结构。
判空条件：L->next == L（与普通链表的 L->next == NULL 不同）。
循环双链表
在循环单链表基础上，头结点的 prior 指向尾结点，尾结点的 next 指向头结点。
判空条件：L->next == L 且 L->prior == L。
终止条件对比
| 对比项 | 普通链表 | 循环链表 |
|---|---|---|
| 尾结点指针 | next = NULL | next = L（指向头结点） |
| 判空条件 | L->next == NULL | L->next == L |
| 遍历终止 | p != NULL | p != L |
尾指针的妙用
如果设置一个尾指针 rear 指向尾结点（而非头指针）：
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 访问尾结点 | O(1) | 直接访问 rear |
| 访问头结点 | O(1) | rear->next |
| 访问第一个数据结点 | O(1) | rear->next->next |
| 两表合并 | O(1) | 仅修改 3 个指针即可完成 |
两个循环单链表的合并可以在 O(1) 时间内完成，这是普通链表做不到的。
静态链表
核心思想
在没有指针的语言中，用数组 + 游标（cursor） 模拟链表。游标存放的是下一个结点在数组中的下标，而非内存地址。
#define MAXSIZE 100
typedef struct { int data; // 数据域 int cursor; // 游标（下一个节点的数组下标）} SLinkList[MAXSIZE];备用链表机制
- Malloc_SL：从备用链表中取出一个空闲结点，返回其下标
- Free_SL：将删除的结点回收到备用链表中
// 分配结点int Malloc_SL(SLinkList space) { int i = space[0].cursor; if (i) space[0].cursor = space[i].cursor; return i;}
// 回收结点void Free_SL(SLinkList space, int k) { space[k].cursor = space[0].cursor; space[0].cursor = k;}特点
- 插入和删除不需要移动元素，只需修改游标
- 仍然不支持随机访问，查找时间复杂度 O(n)
- 容量固定，需预先确定 MAXSIZE
各结构复杂度对比
| 操作 | 顺序表 | 单链表 | 双链表 | 循环单链表（尾指针） | 静态链表 |
|---|---|---|---|---|---|
| 按位查找 | O(1) | O(n) | O(n) | O(n) | O(n) |
| 按值查找 | O(n) | O(n) | O(n) | O(n) | O(n) |
| 插入（已知位置） | O(n) | O(1) | O(1) | O(1) | O(1) |
| 删除（已知位置） | O(n) | O(1) | O(1) | O(1) | O(1) |
| 头插/头删 | O(n) | O(1) | O(1) | O(1) | O(1) |
| 尾插（头指针） | O(1) | O(n) | O(n) | O(1) | O(n) |
| 尾插（尾指针） | O(1) | O(1) | O(1) | O(1) | O(1) |
| 两表合并 | O(n) | O(n) | O(n) | O(1) | O(n) |
| 存储密度 | 高（=1） | 低 | 更低 | 低 | 较低 |
链表的工程应用
链表的变体在实际工程中有广泛应用：
- 栈（Stack）的链式实现——链栈：以链表头部作为栈顶，入栈/出栈均为 O(1)
- 队列（Queue）的链式实现——链式队列：头指针 front 指向头结点，尾指针 rear 指向尾结点，入队 O(1)、出队 O(1)
- 操作系统进程调度：循环链表实现时间片轮转（Round-Robin）调度
- 内存管理：空闲块链表（free list）管理动态内存分配
- LRU 缓存：结合哈希表的双向链表实现 O(1) 的缓存淘汰
考研高频考点
- ⭐ 头插法与尾插法的区别及代码实现（选择题/代码题高频）
- ⭐ 链表逆置的算法设计（算法大题常考）
- ⭐ 单链表 vs 顺序表的优缺点对比（简答题必考）
- ⭐ 插入/删除操作中指针修改的顺序（选择题陷阱）
- ⭐ 带头结点与不带头结点的区别
- ⭐ 双链表插入操作的指针修改顺序（四个指针的顺序）
- ⭐ 循环链表的判空条件（
L->next == L） - ⭐ 尾指针的两表合并操作（O(1)）
- ⭐ 静态链表游标的含义与备用链表管理
- 链表的存储密度（< 1）
- 循环链表遍历的终止条件（
p != L）
关联页面
- 算法分析 — 复杂度分析方法，为链表操作提供理论基础
- 顺序表（Sequential List） — 顺序存储实现，与链表对比的经典参照
- 栈（Stack） — 链栈：链表的栈式应用
- 队列（Queue） — 链式队列：链表的队列式应用
文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！
评论区
