双向链表为什么能 O(1) 删除已知节点？需要注意哪些指针更新？

简化版

双向链表的节点同时保存 prev 和 next，所以已知某个节点时，可以直接找到前驱和后继，把 node.prev.next 指向 node.next，再把 node.next.prev 指向 node.prev，删除过程是 O(1)。

单链表删除已知节点通常难在找前驱；双向链表把前驱指针存在节点里，因此删除已知节点不需要从头遍历。

典型步骤：

如果使用哨兵头尾节点，删除逻辑更简单，因为普通节点永远有前驱和后继：node.prev.next = node.next; node.next.prev = node.prev。

删除链表节点不是“让这个节点消失”这么简单，而是让它的前驱绕过它，直接指向它的后继。单链表节点只有 next，已知 node 时，你能找到后继，却找不到前驱。

单链表：
1 -> 2 -> 3 -> 4
     ^
    node

要删除 2，必须让 1.next = 3
但 node 本身不知道 1 在哪里

所以单链表删除“已知节点”经常需要从 head 开始找前驱，时间是 O(n)。双向链表正是为了解决这类双向导航问题。

双向链表节点有两个方向的连接：prev 指向前驱，next 指向后继。删除一个已知节点时，它自己就携带了足够的信息。

prev <-> node <-> next

删除后：
prev <--------> next

核心操作可以写成：

node.prev.next = node.next;
node.next.prev = node.prev;

这两行表达的是同一件事的两个方向：前驱的后继改成后继，后继的前驱改成前驱。双向链表必须两边都改，否则链表会出现一个方向能遍历、另一个方向坏掉的状态。

如果没有哨兵，删除头节点时 node.prev 是空，删除尾节点时 node.next 是空，需要分别判断。判断并不难，但分支越多越容易漏。

使用哨兵头尾后，结构变成：

headSentinel <-> 真实节点... <-> tailSentinel

真实节点永远不会是物理上的最前或最后，它总有前驱和后继。删除任意真实节点都能统一使用两行代码。很多 LRU 缓存实现都用这种方式，因为缓存每次访问都要移动节点，频繁操作下统一逻辑特别重要。

如果不用哨兵，就必须维护 head 和 tail。删除头节点时，新头应该是旧头的 next；删除尾节点时，新尾应该是旧尾的 prev。

例如只有 1 个节点：

head -> X <- tail

删除后 head 和 tail 都应该变成 null。如果只更新一个，链表状态就不一致。后续插入、遍历、判断是否为空都会出错。

删除完成后，节点已经不属于链表，但它的 prev 和 next 字段可能还指向旧邻居。清空这些字段有两个好处。

第一，避免误用。别人拿到这个节点时，如果看到它还连着旧节点，可能误以为它仍在链表里。第二，帮助垃圾回收。某些语言或运行时中，旧引用会延长对象可达链，导致本该释放的对象暂时无法回收。

node.prev = null;
node.next = null;

这一步不改变渐进复杂度，但能让数据结构状态更干净，尤其适合工程实现。

双向链表删除已知节点是 O(1)，因为不需要遍历。插入到已知节点前后也通常是 O(1)。代价是每个节点多一个 prev 指针，内存占用更高，维护时也要保证两个方向一致。

记忆钩子：双向链表 O(1) 删除靠的不是魔法，而是节点自带前驱；删除时永远记得“前驱改 next，后继改 prev”。

把双向链表删除记成一个局部手术：prev <-> node <-> next 变成 prev <-> next。单链表缺前驱，所以已知节点也难删；双向链表把前驱存在节点里，所以能 O(1)。但这个 O(1) 只针对“节点已经找到”的情况，不包含按值查找。