链表：单链表、双链表与循环链表

学完顺序表之后，很多人会自然产生一个问题：既然数组按下标访问这么快，为什么还需要链表？答案就在顺序表最明显的短板里。顺序表依赖连续空间，访问位置很快，但一旦要在中间插入或删除元素，往往就需要整体搬移大量数据。也就是说，它很适合“按位置读写”，却不一定适合“频繁调结构”。

链表出现的意义，恰恰就是换一种思路来组织数据：不再强求所有元素连续摆放，而是让每个元素各自存放，并通过指针或引用把它们串起来。这样一来，虽然失去了顺序表那种天然的随机访问能力，但却换来了更灵活的结构调整能力。很多中间插入、删除操作，不再需要整体搬移后续元素，而只需要改动少量链接关系。

所以学习链表，最重要的不是记住几个节点指针怎么画，而是理解它代表的是一条和顺序表完全不同的设计路线：

顺序表强调连续存储和快速定位；
链表强调节点分散存储和结构调整灵活。

从这一篇开始，你会第一次非常明显地感受到数据结构里那种经典的“取舍关系”：没有一种结构对所有操作都最优，真正关键的是理解它擅长什么，又牺牲了什么。

一、什么是链表

链表可以先用一句很直观的话来理解：

由一组节点组成，每个节点除了保存数据本身，还保存与其他节点之间的连接关系。

和顺序表最大的不同在于，链表中的元素不要求在内存里连续存放。每个节点可以分散存在不同位置，只是通过“指向下一个节点”的方式连成一条逻辑上的线性序列。

所以链表也同样表示一种线性关系：

第一个节点后面接第二个；
第二个后面接第三个；
直到最后一个节点。

只是这种“前后关系”不再依靠物理位置连续来体现，而是依靠节点之间的链接信息来体现。

二、链表节点里通常有什么

一个最基础的链表节点通常至少包含两部分：

1. 数据域

也就是当前节点真正保存的值。

2. 指针域

也就是指向下一个节点的位置。

如果用一种抽象写法来表示，一个单链表节点大致可以理解成：

1	[data \| next]

其中：

data 表示当前节点数据；
next 表示下一个节点的地址或引用。

这样一来，只要拿到第一个节点，也就是头节点，就可以顺着 next 一路往后找到整条链上的所有元素。

三、为什么链表不支持高效随机访问

这一点正是链表和顺序表最核心的差别之一。

顺序表之所以能 O(1) 按下标访问，是因为元素连续存储，可以直接按偏移量定位。但链表节点是分散的，所以你不能直接“算出第 i 个节点在哪”。

如果要访问链表中第 i 个位置的元素，通常只能：

从头节点出发；
一个节点一个节点往后走；
直到走到目标位置。

所以链表按位置访问通常是 O(n)。

也就是说，链表的代价非常明确：

为了获得结构调整的灵活性，它放弃了顺序表那种快速随机访问能力。

四、链表为什么插入和删除更灵活

这也是链表最有代表性的优势。

如果你已经找到了待操作位置附近的节点，那么链表中的插入和删除，往往只需要修改少量指针关系。

例如，在某个节点 p 后面插入一个新节点 s，大致只需要两步：

让 s.next 指向原本 p 后面的节点；
再让 p.next 指向 s。

删除时也类似：

让前驱节点直接跳过目标节点，改为指向目标节点的后继。

整个过程不需要像顺序表那样整体搬移大量元素。

所以只要已经定位到插入或删除位置，链表的局部结构调整往往很高效。

但这里要特别注意一句：

链表插入删除快，前提通常是你已经找到了目标位置。

如果为了找到这个位置本身就要从头遍历，那总成本未必低。

五、单链表是什么

单链表是最基础、最常见的一种链表形式。它的特点是：

每个节点只保存一个指向后继节点的指针；
整条链通常从头节点开始；
最后一个节点的 next 一般为空。

可以把它想成一条“只能往前走”的单向路径：

1	head -> node1 -> node2 -> node3 -> null

单链表的优点是结构简单，节点额外开销小，实现也直观。很多链表基础题、链表反转、合并链表、快慢指针等内容，都会默认从单链表开始。

六、单链表最典型的操作有哪些

单链表通常会涉及这些高频操作：

头插；
尾插；
按值查找；
按位置查找；
在指定节点后插入；
删除某个节点；
遍历整条链表。

这些操作里最值得重点理解的是：

1. 头插很自然

只需要让新节点指向原头节点，再把头指针改成新节点。

2. 尾插如果没有尾指针，通常要遍历到末尾

所以单链表尾插未必总是快，取决于你是否额外维护尾节点。

3. 删除某个节点通常需要前驱节点

因为你要修改的是“前一个节点的 next”。

这也是单链表的一个典型限制：

你只能顺着往后走；
想回头很麻烦；
很多删除操作都依赖前驱。

七、双链表为什么要多一个指针

双链表是在单链表基础上的一个增强版本。它的每个节点通常包含：

数据域；
指向后继的指针；
指向前驱的指针。

抽象表示大致像这样：

1	[prev \| data \| next]

有了 prev 之后，双链表就不再只能单向前进，而是可以前后双向移动。

这带来的直接好处是：

更容易找到前驱节点；
某些删除操作会更方便；
支持从尾部往前遍历；
更适合实现需要双向移动的结构。

例如浏览器历史记录、LRU 缓存中的双向链表、一些双端队列实现，都会更偏向使用双链表。

八、双链表相比单链表的代价是什么

双链表不是免费升级，它也有明显代价。

1. 每个节点更大

因为多存了一个前驱指针，所以额外空间开销更高。

2. 更新指针更复杂

插入和删除时，不只是改 next，还要同时维护 prev，一不小心就容易出现链接断裂或方向错误。

3. 实现边界更容易出错

尤其是在头节点、尾节点、空链表、只剩一个节点这些场景下，双向维护比单向维护更容易写错。

所以双链表的本质是：

用更多空间和更高维护复杂度，换来更强的双向访问和局部操作能力。

九、循环链表又是什么

循环链表是在普通链表基础上的另一种变形，它的核心特点是：

最后一个节点不再指向空；
而是重新指向头节点。

如果是单向循环链表，大致像这样：

1
2
3

head -> node1 -> node2 -> node3
 ^                         |
 |_________________________|

如果是双向循环链表，则首尾之间的前驱和后继关系也会形成闭环。

循环链表的意义在于：

从任意节点出发都可以继续循环访问；
某些需要“轮转”的问题会更自然；
首尾连接之后，有些边界处理会更统一。

例如约瑟夫问题、循环调度、环形结构建模等场景里，循环链表会更贴切。

十、链表里为什么常常会引入头节点

很多教材和实现里，会额外设置一个“头节点”或者“哨兵节点”。它本身不一定存放有效业务数据，但它的存在能让很多边界情况更统一。

例如：

空链表也可以有一个固定的头节点；
在表头插入、删除时，不必总是单独区分“是不是第一个真实元素”；
某些实现里可以减少大量特判逻辑。

这类“哨兵”思想在数据结构和工程实践里非常常见，不只是链表，后面的树、哈希表、队列等地方也经常会看到类似设计。

所以头节点的价值不只是多一个节点，而是帮助你把边界处理变得更稳定、更一致。

十一、链表的常见复杂度应该怎么理解

链表的复杂度分析，一定要把“是否已经定位到目标位置”这个前提分开看。

1. 头部插入：通常是 `O(1)`

因为只需要改少量指针。

2. 已知节点后插入：通常是 `O(1)`

因为只做局部链接调整。

3. 头部删除：通常是 `O(1)`

直接把头指针后移即可。

4. 按位置查找：通常是 `O(n)`

因为要从头顺着找。

5. 按值查找：通常也是 `O(n)`

因为没有随机访问和索引。

6. 删除指定位置节点

如果已经拿到前驱节点，通常可以做到 O(1)；
如果还得先找前驱，那整体仍然可能是 O(n)。

所以学链表时最容易出错的一点就是：

不能简单说“链表插入删除快”，而要明确是在什么前提下快。

十二、链表和顺序表到底该怎么比较

这一组对比几乎是线性结构学习里最经典的一组。

1. 顺序表的特点

连续存储；
按下标访问快；
中间插入删除通常要搬移大量元素；
更适合随机访问场景。

2. 链表的特点

节点分散存储；
随机访问差；
局部插入删除更灵活；
更适合结构频繁调整的场景。

可以把它们的差别浓缩成一句话：

顺序表擅长“找位置”，链表擅长“改结构”。

当然这句话只是帮助建立直觉，真正使用时仍然要结合具体操作模式和复杂度前提去判断。

十三、链表在真实开发里常出现在哪里

虽然很多现代语言里直接暴露给你的高频容器更像动态数组，但链表的思想在工程里依然非常常见。

例如：

LRU 缓存常用哈希表加双向链表；
某些任务调度结构会用链表维护顺序关系；
操作系统、内核、网络协议栈中经常会看到链表组织节点；
消息队列、空闲块管理、对象池等场景中也常会用到链式结构；
很多复杂结构底层都会借助链表做局部连接和重排。

也就是说，链表不一定总是作为“最终容器”直接暴露给业务开发者，但它在很多底层设计里非常高频。

十四、学习链表时最容易踩的坑

1. 指针更新顺序写错

链表最常见的问题不是概念不懂，而是代码里先后顺序一错，整条链就断了。

2. 忘记处理空链表和单节点链表

很多边界 bug 都出在这里。

3. 删除节点时丢失后续引用

如果修改指针前没有先保存必要信息，后面的节点可能直接找不到。

4. 把“插入删除快”理解成无条件成立

一定要记住，前提通常是已经定位到目标位置。

5. 对单链表、双链表、循环链表的适用场景没有区分

不同变体不是越复杂越好，而是为了服务不同操作需求。

十五、为什么链表是很多指针题的起点

链表很适合作为“指针思维训练场”，因为它会逼着你真正理解：

节点和节点之间是怎么连接的；
修改引用关系时到底发生了什么；
为什么顺序错一步，结果就完全变了；
如何处理前驱、后继、空节点、头尾边界。

后面你在链表里经常会见到这些经典技巧：

快慢指针；
反转链表；
合并两个有序链表；
找中点；
判断环；
删除倒数第 k 个节点。

这些题型的价值，不只是练链表本身，更是在训练你对引用、边界和局部结构变化的掌控能力。

总结

链表的重要性，不只是因为它是线性结构里的另一种实现路线，更因为它非常典型地体现了数据结构中的取舍思想。真正值得先建立起来的，是这些核心认识：

链表通过节点和链接关系组织线性数据，不要求连续存储；
它放弃了顺序表的高效随机访问，换来了更灵活的局部结构调整能力；
单链表适合基础场景，双链表增强了双向操作能力，循环链表则适合环状和轮转型问题；
链表的插入删除是否高效，关键前提是是否已经定位到目标位置；
头节点、哨兵节点等设计能帮助统一边界处理；
真正学会链表，不是只会画几个箭头，而是能理解每次指针修改到底在改变什么结构关系。

把这一篇理解透之后，后面再去学栈和队列时，你会越来越明显地发现：很多抽象数据类型之所以能有不同实现方式，背后其实都是在不同操作需求之间做权衡。而链表，就是理解这种权衡最经典的一课。

参考资源：