单链表和双链表有什么区别？各自适合什么场景？

简化版

单链表每个节点只有一个 next 指针，只能从头往尾单向走；双链表每个节点多一个 prev 指针，能双向遍历，还能 O(1) 地拿到某节点的前驱。双链表增删更灵活（尤其删除已知节点、往前找），代价是每个节点多一个指针的内存开销。需要频繁双向移动/删除任意节点（如 LRU）用双链表，只需单向遍历、省内存用单链表。

详细版

维度	单链表	双链表
指针	只有 `next`	`next` + `prev`
遍历方向	只能正向	正反都行
找前驱节点	O(n)（从头找）	O(1)（直接 `prev`）
删除给定节点	O(n)（需先找前驱）	O(1)（有 `prev`）
内存开销	每节点 1 个指针	每节点 2 个指针
实现复杂度	简单	稍复杂（改指针要维护两个方向）

核心区别就一句：双链表多存了 prev，用「一个指针的空间」换来了「向前的能力」和「O(1) 删除已知节点」。

完整版教学

一、结构差异

单链表节点：

class Node { int val; Node next; }

双链表节点：

class Node { int val; Node prev, next; }

就多一个 prev。但这个 prev 带来的能力差别很大——它让「往回走」和「知道我前面是谁」成为 O(1) 操作。

二、为什么双链表「删除更快」

删除一个节点，本质是让「它的前驱」的 next 跳过它，指向「它的后继」。

单链表：你手里就算已经拿到要删的节点 p，也不知道 p 的前驱是谁，必须从头遍历找到「next 指向 p 的那个节点」，O(n)。
双链表：p.prev 直接就是前驱，p.prev.next = p.next; p.next.prev = p.prev; 两句 O(1) 搞定。

这正是 LRU 缓存用双链表的原因：命中某个节点后要把它 O(1) 地从中间摘下来移到头部，只有双链表能做到。

三、为什么单链表「省内存、够用就好」

双链表每个节点多一个 prev 指针（64 位系统上多 8 字节）。节点数百万级时，这份开销不小。如果业务只需要单向遍历（如遍历、头插、构建栈），单链表完全够用，还省内存、少维护一个方向的指针（改指针时不容易出错）。

四、常见变体

带头结点（哨兵）的链表：在真正的头节点前加一个不存数据的哑节点，让「删除头节点」和「删除中间节点」逻辑统一，减少边界判断。
循环链表：尾节点的 next 指回头节点（单循环），或双向循环（Java 的 LinkedList 就是双向链表，且早期实现带循环特性）。
双向链表 + 哨兵头尾：LRU、LinkedHashMap 常用，插入删除完全不用判 null。

五、怎么选

需要双向遍历、频繁删除任意节点、要 O(1) 拿前驱（LRU、编辑器光标、播放列表前后切歌）→ 双链表。
只单向遍历、内存敏感、逻辑简单（栈、简单队列、一次性遍历）→ 单链表。

Java 的 LinkedList 选择了双向链表，就是为了支持 Deque（两端高效操作）和向前遍历。

六、常见误区与追问

操作	单链表	双链表	差异原因
从头向后遍历	O(n)	O(n)	都能沿 `next` 走
从节点向前走	不支持	O(1) 到前驱	双链表有 `prev`
删除已知节点	通常 O(n) 找前驱	O(1)	是否能直接拿到前驱
每节点指针开销	1 个	2 个	双链表多存 `prev`

记忆钩子：双链表用空间买“回头能力”。只要面试题里出现“已知节点、从中间删除、移动到头尾”，就要想到双链表。

用数字感受内存差异：在 64 位环境里，一个引用通常按 8 字节理解，双链表每个节点比单链表多一个 prev 引用。100 万个节点大约多 1000000 * 8 = 8MB 指针空间，还没算对象头、对齐和业务字段。节点越多，这个代价越不能忽略。

误区：双链表所有操作都比单链表快。 双链表主要提升前驱访问、反向遍历和已知节点删除，普通从头遍历仍然是 O(n)。
误区：单链表删除节点一定做不到 O(1)。 如果题目给的是“非尾节点且允许复制后继值”的特殊删除，可以用覆盖法；常规删除已知节点仍需前驱。
误区：双链表只是在单链表上多写一个字段，没有额外风险。 插入删除要同时维护 prev 和 next，漏改任一方向都会破坏结构。
追问：LRU 为什么常用双链表？ 命中缓存节点后要 O(1) 从中间摘除并移动到头部，必须快速拿到前驱和后继。
追问：什么时候单链表更合适？ 只需要单向遍历、头插、栈式结构或内存敏感时，单链表更简单省空间。
追问：哨兵节点有什么价值？ 哨兵头尾能统一空链表、删头、删尾和中间删除逻辑，减少 null 分支。

七、加强记忆

单链表只有 next、单向走、删除已知节点要先 O(n) 找前驱；双链表多个 prev，能双向遍历、O(1) 拿前驱、O(1) 删除已知节点，代价是每节点多一个指针的内存。频繁双向移动/删除（LRU）用双链表，只需单向遍历省内存用单链表。Java 的 LinkedList 是双向链表。

简化版

详细版