← 中文资源

简体中文版本

支持 O(1) 删除的双向链表

实现支持 O(1) 尾部插入、头部插入和已知节点删除的双向链表,并提供迭代器与数组转换。

阅读英文原文

功能说明

双向链表的每个节点保存前后指针,支持 O(1) 头尾插入和已知节点删除。该实现提供 push、unshift、remove、toArray 与迭代器,并维护长度计数,适合实现 LRU 列表、撤销历史和任务队列。toArray 通过迭代器遍历,不暴露内部节点结构。

关键代码

push 把新节点接到 tail,unshift 接到 head,同时更新相邻节点指针。remove 根据节点是否为头尾更新 head 与 tail,再连接前后节点,最后清空该节点的指针并把计数减一。迭代器从 head 沿 next 遍历,直到 null 为止。

if (node.prev) node.prev.next = node.next;
else this.headNode = node.next;
if (node.next) node.next.prev = node.prev;
else this.tailNode = node.prev;
node.prev = null;
node.next = null;
this.count -= 1;

使用注意

remove 假设节点属于当前链表,传入外部节点可能破坏结构或误删。节点删除后指针被清空,不能重复删除。该实现不是线程安全的。迭代过程中修改链表可能导致跳过或重复访问,应先把节点收集到数组再修改。空链表删除应返回 false。

验证方式

断言 push 三个节点后 length 为 3,toArray 返回原顺序。unshift 后顺序改变且 length 增加。删除中间节点后长度减一,前后连接正确。删除头尾节点会更新边界。迭代器按顺序产出所有值,重复删除同一节点返回 false。