双向链表与循环链表（进阶）
复习
- 单向链表：节点保存数据并指向下一个节点
- 引用与指针：保存数据的位置而非内容
- 数组与链表：连续与链式各有取舍
本章为进阶内容，零基础读者可以跳过，不影响后续阅读。
TL;DR
- 双向链表每个节点还保存指向前一个的指针
- 它让“往回走”成为可能，删除也更方便
- 循环链表首尾相接，适合循环往复的场景
- 多存链接换来更多操作优势，也多花一点空间
正文
单向链表只能一路向前。如果走到一半发现走过了头，想退回去，就只能从头再来。这一章看看两个常见的改进。
双向链表：能往回走
双向链表（doubly linked list）的每个节点多存一个指针：不仅指向下一个，也指向前一个。
多出来的这个指针，换来两个直接的好处：
- 可以反向遍历：想往前、往后都行
- 删除更方便：只要拿到目标节点本身，就能借助前驱指针直接把它摘掉，不必再从头找到它前面那个
代价也是显然的：每个节点多占一个指针的空间，插入和删除时要多维护一处指针，容易出错。
循环链表：首尾相接
循环链表（circular linked list）则把最后一个节点的指针指回第一个，首尾相连，形成一个环。
它适合那些循环往复的场景：转了一圈又回到开头，天然对应“轮流”“轮转”的逻辑。比如：
- 多个任务轮流执行
- 固定大小的缓冲区循环使用
当然，成环也意味着遍历要小心：不能简单地“走到空就停”，得设定好终止条件，否则会一圈圈转下去。
多一份链接，多一份能力
这两个变体的思路是一致的：多保存一些链接信息，就能换来更多的操作能力。
这和前面反复出现的主线一模一样：用空间（多存指针）换时间或便利。没有免费的增强，每多一分能力，就多一分空间开销和实现复杂度——是否值得，还是要看你主要做哪些操作。
至此，我们有了数组、链表这两类“线性结构”。接下来，看看两种更强调“操作顺序”的抽象：栈和队列。
思考题 1
双向链表比单向链表多保存了什么？它换来了哪些操作上的优势？
思考题 2
循环链表适合什么样的场景？
小结
知识点
- 双向链表节点保存前驱与后继指针
- 双向链表支持反向遍历，删除更方便
- 循环链表首尾相接，适合轮转场景
- 变体都体现了“多存链接换能力”的取舍
参考资料
- Wikipedia(zh)：双向链表：每个节点保存前后两个指针
- Wikipedia(zh)：循环链表：首尾相接形成环的链表
思考题答案（仅供参考）
思考题 1
多保存了指向“前一个节点”的指针。换来的优势是：可以反向遍历；删除某个已知节点时，不必再从头去找它的前驱，直接借助前驱指针就能摘掉它，操作更方便。
思考题 2
适合需要循环往复的逻辑，比如多个任务轮流执行、固定大小缓冲区反复使用等。因为首尾相接，转一圈能自然回到起点，正对应“轮流”的语义。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪