双向链表
双向链表的节点同时保存 next 和 prev，链表保存 head 与 tail。它支持反向遍历；已持有目标节点时，可用 O(1) 将其移除，不必再找前驱。
代价是额外内存与指针维护。中间插入要写新节点的两个指针，再写邻居各一个指针，共四次。漏写一侧可能让正向和反向遍历看到不同的链。
双向链表如何工作
每个节点像两端都有连接器的车厢。已找到车厢后，让前后邻居互连，就能把它移出。
在 pred 与 succ 之间插入时，依次写 newNode.prev = pred、newNode.next = succ、pred.next = newNode、succ.prev = newNode。动画分两拍：新节点先指向两侧，邻居再指回新节点。
删除内部节点时，node.prev、node.next 已给出邻居。执行 node.prev.next = node.next 和 node.next.prev = node.prev 即可，时间 O(1)。但按值找到节点仍需 O(n)。单链表若只持有目标节点，还需知道前驱；双向链表用额外指针保存了这项信息。
search 从 head 沿 next 前进，search_back 从 tail 沿 prev 后退。比较规则相同，遍历方向相反。
容量滑块 4–10、默认 7，对应画布大小和代码的 max。它不是双向链表的固定容量要求。
逐步演示
从空表开始：
- 头插 5：
5.prev、5.next都是 null，head、tail同时指向 5。 - 头插 8：先
8.next = 5、8.prev = null，再5.prev = 8，head改为 8。得到8 ⇄ 5。 - 尾插 3：
tail直接定位 5，无需遍历。写3.prev = 5、3.next = null，再5.next = 3，tail改为 3。得到8 ⇄ 5 ⇄ 3。 - 索引 1 插入 7：
curr到索引 0 的前驱 8。写7.prev = 8、7.next = 5，再8.next = 7、5.prev = 7。得到8 ⇄ 7 ⇄ 5 ⇄ 3。 - 正向搜索 7：索引 0 的
8 ≠ 7，索引 1 的7 = 7，返回 1。 - 反向搜索 5：从尾部索引 3 比较
3 ≠ 5，沿prev到索引 2，5 = 5，返回 2。 - 删除 7：正向搜索让
curr位于目标 7，而非前驱。其prev为 8、next为 5，写8.next = 5、5.prev = 8，移出 7。结果8 ⇄ 5 ⇄ 3。
画布上方显示 next，下方显示 prev。待插节点在指针写入完成前留在上方；删除时游标指向目标，两条旁路箭头同时越过它。
时间与空间复杂度
| 操作 | 成本 | 原因 |
|---|---|---|
| 索引访问 | O(n) | 从一端沿指针遍历 |
| 头插 | O(1) | 常数次写入 |
| 尾插 | O(1) | 已保存 tail |
| 索引 k 插入 | O(k) | 本课正向定位前驱，再接入 |
| 删除已持有节点 | O(1) | prev、next 给出两侧 |
| 按值删除 | O(n) | 查找 O(n)，移除 O(1) |
| 正向或反向搜索 | O(n) | 逐节点比较 |
| 空间 | O(n) | 每节点一个值、两个指针 |
本课相较只保存 head 的单链表，增加了反向链接与 tail。反向链接支持逆向遍历和已知节点删除；尾插的 O(1) 则来自维护 tail，单链表也可单独增加尾指针。
边界情况
- 空表插入：唯一节点成为
head和tail，两侧为空。 - 删除头部：
node.prev为空，改写head = node.next；若新头存在，再设head.prev = null。 - 删除尾部：改写
tail = node.prev；若新尾存在，再设tail.next = null。 - 删除唯一节点：两侧都为空，
head、tail一起清空。 - 值不存在：正向或反向走到末尾，删除返回
False，搜索返回-1，不抛异常。 - 插入索引越过末尾：展示代码缺少完整边界检查，会走到空引用；可视化停止并说明。
k = 0调用insert_head，k = size调用insert_tail。
常见错误
- 只更新一个方向。 写
pred.next = newNode却漏掉succ.prev = newNode，正向可能正常，反向会跳过新节点。 - 忘记端点引用。 删除头尾后必须重设
head、tail；唯一节点要同时处理两者。 - 已有节点还遍历找前驱。
prev已保存前驱，重复遍历丢失了双向链接的优势。 - 默认使用双向链表。 若只从单端压入、弹出和正向遍历，额外指针可能没有收益。根据实际操作选择单链表或数组。