Menu
CoddyTech
开始学习

双向链表

最后更新

双向链表是一种每个节点都有两个指针的链表：next（指向后一个节点）和 prev（指向前一个节点）。多出来的这个反向链接让你可以双向遍历；当你已经持有某个节点的引用时，还能以 O(1) 删除它，因为可以直接找到它的前驱，而不必从头节点一路走过去。点击上方的“播放”，观察节点如何双向连接和重新连接。

代价是每个节点多一个指针，维护工作也更多：每次插入和删除都必须同时更新相邻节点的 next 和 prev。很多双端队列和 LRU 缓存都基于这种结构，因为它们需要从两端快速移除元素。

时间复杂度

操作复杂度说明
在头部或尾部插入O(1)需要头指针和尾指针
删除已知节点O(1)直接找到 prev，无需遍历
查找O(n)仍然是线性扫描
按下标访问O(n)不支持随机访问

单向链表与双向链表对比

方面单向链表双向链表
每个节点的指针数1 (next)2 (next + prev)
反向遍历不支持支持
删除已知节点O(n)（要找 prev）O(1)
内存开销较低较高

示例演算

通过追加构建 [10, 20, 30]，然后删除节点 20：

步骤结构操作
开始null空链表：head 和 tail 都是 null
追加 1010第一个节点；head 和 tail 都指向它，prev = next = null
追加 2010 <-> 20令 10.next = 20，20.prev = 10；tail = 20
追加 3010 <-> 20 <-> 30令 20.next = 30，30.prev = 20；tail = 30
删除 2010 <-> 30借助 20.prev 和 20.next：以 O(1) 令 10.next = 30，30.prev = 10

什么时候使用双向链表

适合使用的情况不适合使用的情况
需要双向遍历或拼接只会向前移动，单向链表更轻量
要删除已持有引用的任意节点（O(1)）主要按位置访问，应使用数组以获得 O(1) 访问
要实现双端队列、LRU 缓存或屏幕上的撤销历史内存紧张，额外的 prev 指针会让链接开销翻倍
频繁在两端插入和移除元素数据量小且很少变化，复制数组更省事

Doubly Linked List 代码

简洁、可运行的 Doubly Linked List 实现，提供 Python, JavaScript, Java, C++, C 版本。选择一种语言，复制代码，或在 Coddy 在线编辑器中直接打开。

Doubly Linked List 的 Python 代码

Python
1class Node:2    def __init__(self, value):3        self.value = value4        self.prev = None5        self.next = None6
7
8class DoublyLinkedList:9    def __init__(self):10        self.head = None11        self.tail = None12
13    def append(self, value):14        node = Node(value)15        if self.tail is None:16            self.head = self.tail = node17            return18        # Wire both directions: old tail <-> new node19        node.prev = self.tail20        self.tail.next = node21        self.tail = node22
23    def prepend(self, value):24        node = Node(value)25        if self.head is None:26            self.head = self.tail = node27            return28        node.next = self.head29        self.head.prev = node30        self.head = node31
32    def forward(self):33        values, current = [], self.head34        while current:35            values.append(current.value)36            current = current.next37        return values38
39    def backward(self):40        values, current = [], self.tail41        while current:42            values.append(current.value)43            current = current.prev44        return values45
46
47lst = DoublyLinkedList()48for value in [2, 3, 4]:49    lst.append(value)50lst.prepend(1)51
52print("Forward: ", lst.forward())53print("Backward:", lst.backward())
在 Python 在线编辑器中运行这段代码

双向链表常见问题

单向链表和双向链表有什么区别？
单向链表的每个节点只有一个指针（next），所以只能向前移动。双向链表多了一个 prev 指针，可以反向遍历，并以 O(1) 删除已持有引用的节点，代价是每个节点多一个指针，每次修改都要更新两个链接。
什么时候值得为双向链表付出额外的内存？
当你需要反向遍历，或者需要以 O(1) 删除已经引用的任意节点时。典型场景是双端队列和 LRU 缓存，其中的条目会频繁地从两端移动和淘汰。
为什么双向链表能以 O(1) 删除节点？
删除一个节点时，必须把它的前驱和后继连起来。在单向链表中，你得从头节点一路走过去才能找到前驱（O(n)）；在双向链表中，节点的 prev 指针直接给出前驱，所以重新连接只需 O(1)。
双向链表和数组，该用哪个？
如果需要按下标 O(1) 访问、对缓存友好的遍历，并且插入大多发生在末尾，就用数组。如果经常在已有节点引用的前提下在中间或两端插入、删除，就用双向链表，因为这只需 O(1)，而数组需要 O(n) 的移动。数组在内存和局部性上占优，链表在结构修改上占优。
双向链表中的哨兵节点是什么？
哨兵节点（也叫虚拟节点）是放在头节点之前和/或尾节点之后的占位节点，让链表永远不会真正为空。它省去了对 head、tail 以及边界插入和删除的 null 检查，让每个操作都走同一套重新连接的代码。很多生产环境中的 LRU 缓存实现都用两个哨兵，避免对两端做特殊处理。
从双向链表中删除节点时，最常见的 bug 是什么？
删除第一个或最后一个节点时，忘了更新 head 或 tail，结果留下一个指向已释放节点的悬空指针。在重新连接相邻节点之前，一定要检查 node.prev 是否为 null（需要更新 head），以及 node.next 是否为 null（需要更新 tail）。

相关资源

更多可视化

Coddy 编程语言插图

在 Coddy 掌握算法

开始