1. 概述
本文将介绍一种常用的数据结构：链表（Linked List）。
我们会讲解链表的基本概念、核心操作、不同变种，并重点介绍双向链表（Doubly Linked List, DLL），以及它的一些实际应用场景。
2. 链表简介
链表是一种动态数据结构，用于在内存中组织数据。与数组不同，链表不需要在声明时指定固定大小，也无需连续的内存空间，因此在处理动态数据时更加灵活。
2.1 链表结构
链表由一系列节点（Node）组成，每个节点包含两个部分：
- 数据（Data）
- 指向下一个节点的指针（Pointer）
结构示意如下：
在代码中可以这样定义一个节点结构：
define structure Element {
variable,
Element *next,
}
此外，我们还需要一个结构来管理整个链表，通常称为链表头（Head）：
define structure L1 {
Element *first,
}
整个链表的结构如下图所示：
最后一个节点指向 null，表示链表结束。
2.2 优势
- 动态扩容，无需预先分配内存
- 插入和删除效率高（无需移动元素）
- 不依赖连续内存空间
3. 链表的基本操作
链表支持以下几种基本操作：
✅ 遍历（Traversal）：从头到尾依次访问每个节点
✅ 插入（Insertion）：可以在任意位置插入新节点
✅ 删除（Deletion）：可以从任意位置删除节点
✅ 更新（Update）：修改某个节点的值
✅ 查找（Search）：判断某个值是否存在
✅ 排序（Sort）：对链表中的节点排序
✅ 合并（Merge）：将两个链表合并为一个
3.1 插入示例
如下图所示，可以在链表头部、中部或尾部插入新节点：
3.2 删除示例
删除节点时，只需修改前后节点的指针即可：
4. 链表的变种
链表有三种主要变体：
| 类型 | 特点 |
|---|---|
| 单向链表（Singly Linked List） | 每个节点只指向下一个节点 |
| 循环链表（Circular Linked List） | 尾节点指向头节点，形成环 |
| 双向链表（Doubly Linked List） | 每个节点同时指向前一个和后一个节点 |
4.1 单向链表
- 插入删除效率高
- 只能向前遍历
- 内存占用相对较小
4.2 循环链表
- 尾节点指向头节点，形成闭环
- 常用于实现队列等数据结构
- ⚠️ 容易造成死循环，需小心处理终止条件
4.3 双向链表（后续重点）
我们将在下文详细介绍双向链表的结构和优势。
5. 链表的应用场景
链表广泛应用于多种数据结构和实际场景中：
- ✅ 实现栈（Stack）、队列（Queue）
- ✅ 图的邻接表（Adjacency List）
- ✅ 稀疏矩阵（Sparse Matrix）表示
- ✅ 哈希表（HashMap）中解决冲突
- ✅ 内存动态分配
- ✅ 文件系统目录管理
- ✅ 多项式运算
实际生活中的例子：
- ✅ 音乐播放器：每首歌曲作为节点，可顺序或逆序播放
- ✅ 图片浏览器：图片之间通过“上一张”、“下一张”切换
6. 双向链表（Doubly Linked List）
6.1 定义
双向链表的每个节点不仅包含指向下一个节点的指针，还包含指向前一个节点的指针。
结构示意如下：
6.2 优势
- ✅ 支持双向遍历
- ✅ 插入删除效率更高（无需遍历查找前一个节点）
- ✅ 更适合需要频繁回溯的场景
6.3 代码结构定义
define structure Element {
variable,
Element *next,
Element *previous,
}
控制结构：
define structure L2 {
Element *first,
}
6.4 踩坑提醒
- ❌ 每次插入或删除节点时，需要同时处理前后两个指针，逻辑更复杂
- ❌ 内存占用比单向链表稍大（每个节点多一个指针）
7. 双向链表的实际应用
双向链表在很多实际系统中都有广泛应用：
- ✅ 浏览器历史记录：实现“前进”、“后退”功能
- ✅ 操作系统：实现“撤销”、“重做”功能
- ✅ 缓存替换策略（如LRU Cache）
- ✅ 进程调度
- ✅ 实现其他数据结构：如二叉树、栈、哈希表等
8. 总结
本文我们介绍了链表的基本结构、操作、变种及其应用场景，重点讲解了双向链表的实现和优势。
| 类型 | 是否可逆 | 插入效率 | 应用场景 |
|---|---|---|---|
| 单向链表 | ❌ | 高 | 一般链式结构 |
| 循环链表 | ❌ | 高 | 队列、定时任务 |
| 双向链表 | ✅ | 更高 | 撤销、历史记录、缓存 |
✅ 链表是动态内存管理、数据结构实现的重要基础。
✅ 双向链表在需要频繁回溯的场景中表现更优。
如需更深入了解链表底层实现或性能优化，可以进一步研究其在不同语言中的实现方式（如 Java 中的 LinkedList）。