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）。