双向链表

9 双向链表

1. 当一个节点没有任何变量指向它(临时变量指向它也会被回收,因为临时变量会消失)的时候,它就会被自动回收

补充

补充：双向链表（Doubly Linked List） 每个节点除了 value 还持有 prev 与 next 两个指针，分别指向前驱和后继节点。

• 优点：可以 O(1) 向前遍历；删除已知节点 O(1)（不必像单链表那样先找到前驱）；适合实现 LRU 缓存、浏览器历史栈等需要双向移动的场景。
• 缺点：每个节点多一个指针，空间开销更大；插入/删除时需要同时维护 prev/next 两边指针，容易遗漏。

class Node {
  constructor(val) {
    this.val = val;
    this.prev = null;
    this.next = null;
  }
}
class DoublyLinkedList {
  constructor() { this.head = null; this.tail = null; }
  append(val) {
    const n = new Node(val);
    if (!this.head) this.head = this.tail = n;
    else { n.prev = this.tail; this.tail.next = n; this.tail = n; }
  }
  remove(node) {
    if (node.prev) node.prev.next = node.next; else this.head = node.next;
    if (node.next) node.next.prev = node.prev; else this.tail = node.prev;
  }
}

来源整理自：我的有道云笔记