链表实现：双链表与单链表的完整 Java 实现
侧重：链表的工程级实现（虚拟头尾节点、头尾引用、内存管理）、完整的增删查改操作
核心实现技巧
1. 同时持有头尾节点引用
在实际开发中，双链表通常会同时持有头尾节点的引用，以优化尾部操作性能：
| 操作 | 无尾引用 | 有尾引用 |
|---|---|---|
| 尾部添加 | O(N) 需遍历 | O(1) |
| 尾部删除 | O(N) 需找前驱 | O(1)（单链表仍需遍历前驱） |
单链表的权衡：
- 持有尾引用可以 O(1) 添加，但删除时仍需遍历找前驱
- 删除尾节点时，正好需要遍历到倒数第二个节点，可以顺便更新尾引用
2. 虚拟头尾节点（Dummy Head/Tail）
这是本文的核心技巧，在 链表基础 中已提及虚拟头结点，本文扩展到虚拟头尾节点：
原理：
- 创建链表时就创建虚拟头节点（dummyHead）和虚拟尾节点（dummyTail）
- 无论链表是否为空，这两个节点都存在
- 避免空指针问题，简化边界条件处理
示例：
空链表：dummyHead <-> dummyTail
添加 1,2,3：dummyHead <-> 1 <-> 2 <-> 3 <-> dummyTail
优点：
- 统一头部、尾部、中间插入/删除的逻辑
- 无需单独处理空链表边界情况
- 代码更简洁
注意：
- 虚拟节点是内部实现，对外不可见（如
get(index)从真实节点开始计算） - 虚拟尾节点对双链表有用，对单链表作用不大
3. 内存泄露问题
本文澄清了链表删除中的内存管理误区：
Java 场景：
// 删除单链表头结点
head = head.next; // 原头结点 1 的 next 仍指向 2
为什么没问题？
- Java 垃圾回收判断对象是否被别人引用，不关心对象是否引用别人
- 原头结点
1虽然还指向2，但没有其他指针引用它，所以会被 GC 回收
最佳实践：
- 删除节点时，仍建议把被删除节点的指针置为 null
- 不会有性能代价，还可能避免潜在问题
代码实现要点
双链表实现（推荐）
节点结构：
private static class Node<E> {
E val;
Node<E> next;
Node<E> prev;
}
关键设计：
- 构造函数初始化虚拟头尾节点，互相指向对方
addLast：在tail.prev和tail之间插入addFirst：在head和head.next之间插入remove：直接修改前驱和后继的指针
单链表实现
节点结构：
private static class Node<E> {
E val;
Node<E> next;
}
关键设计：
- 使用虚拟头节点（head），但不使用虚拟尾节点
- 持有真实尾节点引用（tail），优化尾部添加
removeLast仍需遍历找前驱（这是单链表的固有局限）
相关概念
相关实体
- labuladong：算法学习平台作者
验证方法
本文实现可通过 LeetCode 707 设计链表 验证：
- 注意 API 名字需要调整（本文用
addFirst/removeLast等，707题用addAtHead/addAtTail等） - 虚拟头尾节点技巧可大幅简化实现
总结
本文提供了工程级的链表实现，核心在于虚拟头尾节点和头尾引用两大技巧。双链表实现更优雅（O(1) 尾部操作），单链表实现更简单但尾部删除仍是 O(N)。理解这些实现技巧，对掌握链表这一基础数据结构至关重要。