双链表（Doubly Linked List）
双链表是链表的一种形式，每个节点包含两个指针（prev + next），支持双向遍历。
节点结构
class Node<E> {
E val; // 节点值
Node<E> next; // 后继指针（指向下一个节点）
Node<E> prev; // 前驱指针（指向前一个节点）
}
基本特性
| 特性 | 说明 |
|---|---|
| 指针数量 | 2个（prev + next） |
| 遍历方向 | 双向（可前可后） |
| 内存开销 | 较大（每个节点多存一个指针） |
| 操作复杂度 | 稍复杂（需维护两个指针） |
操作时间复杂度
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 查/改（给定索引） | O(N) | 可从头或尾开始遍历 |
| 头部插入 | O(1) | 新节点成为头，维护prev/next |
| 尾部插入 | O(1)* | 需持有尾引用 |
| 中间插入 | O(N) | 需先找到插入位置 |
| 头部删除 | O(1) | 更新头指针，清理旧头结点 |
| 尾部删除 | O(1)* | 需持有尾引用且有前驱指针 |
| 中间删除 | O(N) | 若已知节点引用则为O(1) |
工程实现要点
1. 同时持有头尾节点引用
final private Node<E> head, tail; // 虚拟头尾节点（通常用final）
private int size;
优点：
- 尾部添加 O(1)：在
tail.prev和tail之间插入 - 尾部删除 O(1)：直接访问
tail.prev（前驱指针） - 可从头或尾开始遍历，优化查找性能
2. 虚拟头尾节点（Dummy Head/Tail）
这是双链表实现的核心技巧：
public MyLinkedList() {
this.head = new Node<>(null); // 虚拟头节点
this.tail = new Node<>(null); // 虚拟尾节点
head.next = tail;
tail.prev = head;
this.size = 0;
}
效果：
空链表：dummyHead <-> dummyTail
添加 1,2,3：dummyHead <-> 1 <-> 2 <-> 3 <-> dummyTail
优点：
- 统一头部、尾部、中间的操作逻辑
- 避免空指针问题，无需单独处理边界情况
- 代码更简洁
注意：
- 虚拟节点是内部实现，对外不可见
- 如
get(index)从真实节点（head.next）开始计算
3. 插入操作示例
在节点 p 前插入新节点 x：
Node<E> prev = p.prev;
// prev <-> p
x.prev = prev;
x.next = p;
prev.next = x;
p.prev = x;
// prev <-> x <-> p
4. 删除操作示例
删除节点 x：
Node<E> prev = x.prev;
Node<E> next = x.next;
// prev <-> x <-> next
prev.next = next;
next.prev = prev;
x.prev = null; // 清理指针（好习惯）
x.next = null;
// prev <-> next
完整实现参考
参见：链表实现
与单链表对比
| 特性 | 单链表 | 双链表 |
|---|---|---|
| 指针数量 | 1个（next） | 2个（prev + next） |
| 遍历方向 | 单向 | 双向 |
| 内存开销 | 小 | 大（多一个指针） |
| 删除尾节点 | O(N)（需找前驱） | O(1)（有直接前驱指针） |
| 实现复杂度 | 简单 | 稍复杂 |
| 工程使用 | 较少 | 主流（Java LinkedList等） |