双向链表（doubly linked list）与单向链表（singly linked list）有何不同？

Question

Accepted Answer

一个**双向链表**给每个节点赋予**两个** pointers — `next` *和* `prev` — 这样你可以在**两个方向**上遍历，并且当你已持有该节点的引用时可以在 O(1) 时间内删除它（无需从头部走到前驱节点）。 ## 结构 ```text null <- [10] <-> [20] <-> [30] -> null prev/next links in BOTH directions ``` ## 已知节点的 O(1) 删除 ```python class Node: def __init__(self, val): self.val, self.prev, self.next = val, None, None def remove(node): # O(1) — no traversal needed if node.prev: node.prev.next = node.next if node.next: node.next.prev = node.prev ``` 在*单向*链表中，删除一个节点需要先找到它的前驱节点 → **O(n)**。 ## 比较 | 方面 | 单向 | 双向 | |---|---|---| | 每个节点的 pointers | 1 (next) | 2 (next, prev) | | 反向遍历 | 否 | 是 | | 删除已知节点 | O(n) | **O(1)** | | 内存开销 | 较低 | 较高 | ## 何时使用 - **双向：** LRU 缓存、浏览器历史、撤销/重做以及任何需要从中间 O(1) 删除的数据结构。 - **单向：** 当内存紧张且仅需前向遍历时。 ## 为什么这很重要 O(1) 时间从已知节点移除的特性是使双向链表成为**LRU 缓存**中 hash map 搭档的关键。额外的 `prev` pointer 用内存开销换取了双向移动的灵活性和常数时间删除的能力。

方面	单向	双向
每个节点的 pointers	1 (next)	2 (next, prev)
反向遍历	否	是
删除已知节点	O(n)	O(1)
内存开销	较低	较高