链表操作与双向链表实现

链表的插入、删除、访问复杂度是多少？

操作	单向链表	双向链表
已知前驱时插入	$O(1)$	$O(1)$
已知节点时删除	$O(n)$, 需找前驱	$O(1)$
按下标插入/删除	$O(n)$, 需先定位	$O(n)$
访问第 k 个节点	$O(n)$	$O(n)$

• 结论: 双向链表用 prev 换来了"已知节点即可 $O(1)$ 删除";
• 代价: 每个节点多存一个引用;

双向链表的插入和删除如何改指针？

• 插入 node 到 position 之后: 先接后继, 再接前驱, 最后回填后继的 prev;
• 删除 node: 前驱的 next 指向 node.next, 后继的 prev 指向 node.prev;
• 边界: 后继为空时只改前驱的 next;

class DoublyLinkedListNode<T> {
  value: T;
  next: DoublyLinkedListNode<T> | null;
  prev: DoublyLinkedListNode<T> | null;
  constructor(
    value: T,
    next: DoublyLinkedListNode<T> | null = null,
    prev: DoublyLinkedListNode<T> | null = null,
  ) {
    this.value = value;
    this.next = next;
    this.prev = prev;
  }
}

class DoublyLinkedList<T> {
  head = new DoublyLinkedListNode<T>(null as T); // 头哨兵
  size = 0;

  find(value: T): DoublyLinkedListNode<T> | null {
    let node = this.head.next;
    while (node) {
      if (node.value === value) return node;
      node = node.next;
    }
    return null;
  }

  insert(node: DoublyLinkedListNode<T>, position: DoublyLinkedListNode<T>): void {
    const next = position.next;
    node.next = next;
    node.prev = position;
    position.next = node;
    if (next) next.prev = node;
    this.size += 1;
  }

  delete(node: DoublyLinkedListNode<T>): boolean {
    const before = node.prev;
    if (!before) return false;
    before.next = node.next;
    if (node.next) node.next.prev = before;
    this.size -= 1;
    return true;
  }
}

为什么实现里要维护 size？

• 用途: 空表判定与容量判断不必每次遍历;
• 一致性: insert 加一, delete 减一, 与指针改动同时发生;