HOWTO · Java
Java 中的双向链表
在本教程中，我们将讨论 Java 中的双向链表
本页内容
双向链表中的每个节点都连接到前一个和后一个节点，因此可以向两个方向遍历。如果代码已经持有某个节点，也可以通过更新相邻引用将其从链表中移除。Java 的 LinkedList 提供了现成的实现；基于 Node 的自定义链表，则适合用来学习这些链接的工作方式，或在项目需要节点级行为时使用。
什么是双向链表？
每个节点存储一个值和两个引用：next 与 previous（通常也写作 prev）。链表会记录第一个节点（头节点），通常也会记录最后一个节点（尾节点）。头节点没有前驱节点，尾节点没有后继节点。Node 通过引用连接，不必存放在相邻的内存位置。
对于相邻节点 a 和 b，如果 a.next == b 且 b.prev == a，两者的链接就相互对应。从头节点沿 next 遍历可以正向移动；从尾节点沿 prev 遍历可以反向移动。单向链表只存储指向后续节点的引用，因此无法从已知节点直接移到它的前驱节点。
使用 Java 的 LinkedList 类
对于一般的应用程序代码，可以先使用 java.util.LinkedList<E>；它同时实现了 List<E> 和 Deque<E>。它支持 addFirst、addLast、get、set、remove、peekFirst 和 peekLast 等操作。ListIterator<E> 可以通过 next() 向前移动，也可以通过 previous() 向后移动。
例如，创建一个 LinkedList<String>，在两端添加值，再用 listIterator() 按顺序读取。若要反向遍历，先通过 while (it.hasNext()) it.next(); 将迭代器移到末尾，然后在 it.hasPrevious() 为真时调用 previous()。Java 集合负责管理内部节点；调用者应使用公开方法，而不是直接访问节点引用。
不要假设所有操作都是常数时间。在任一端添加或移除元素需要常数时间。按索引查找元素，或通过搜索查找某个值，所需时间与遍历距离成正比。通过 ListIterator 插入或移除元素时，如果迭代器已经位于目标位置，操作需要常数时间；但移动到该位置可能需要线性时间。按索引调用 set 也必须先定位到该索引。
在 Java 中实现双向链表
下面的独立程序同时维护 head 和 tail。它通过 linkBetween 辅助方法集中处理插入时常见的引用更新，并由 unlink 重新连接被移除节点两侧的节点。checkLinks 方法会检查两个方向的链接是否一致，遍历方法则展示节点顺序。将程序保存为 Main.java，即可使用 Java 编译器编译并运行。
运行这个独立示例：
本节中的代码以及显示的标签或输出仍为英文。
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.ListIterator;
public class Main {
static final class Node {
final int value;
Node previous;
Node next;
Node(int value) {
this.value = value;
}
}
static final class DoublyLinkedList {
private Node head;
private Node tail;
private int size;
void addLast(int value) {
linkBetween(new Node(value), tail, null);
}
void addFirst(int value) {
linkBetween(new Node(value), null, head);
}
void insertAt(int index, int value) {
if (index < 0 || index > size) {
return;
}
if (index == size) {
addLast(value);
} else if (index == 0) {
addFirst(value);
} else {
Node right = nodeAt(index);
linkBetween(new Node(value), right.previous, right);
}
}
int removeAt(int index) {
if (index < 0 || index >= size) return -1;
Node target = nodeAt(index);
int value = target.value;
unlink(target);
return value;
}
private Node nodeAt(int index) {
if (index < 0 || index >= size) return null;
if (index < size / 2) {
Node current = head;
for (int i = 0; i < index; i++) current = current.next;
return current;
}
Node current = tail;
for (int i = size - 1; i > index; i--) current = current.previous;
return current;
}
private void linkBetween(Node node, Node left, Node right) {
node.previous = left;
node.next = right;
if (left == null) head = node;
else left.next = node;
if (right == null) tail = node;
else right.previous = node;
size++;
}
private void unlink(Node node) {
if (node.previous == null) head = node.next;
else node.previous.next = node.next;
if (node.next == null) tail = node.previous;
else node.next.previous = node.previous;
node.previous = null;
node.next = null;
size--;
}
String forward() {
StringBuilder result = new StringBuilder();
for (Node node = head; node != null; node = node.next) {
if (result.length() > 0) result.append(" <-> ");
result.append(node.value);
}
return result.toString();
}
String backward() {
StringBuilder result = new StringBuilder();
for (Node node = tail; node != null; node = node.previous) {
if (result.length() > 0) result.append(" <-> ");
result.append(node.value);
}
return result.toString();
}
boolean checkLinks() {
int count = 0;
Node previous = null;
for (Node node = head; node != null; node = node.next) {
if (node.previous != previous) return false;
previous = node;
count++;
}
if (previous != tail || count != size) return false;
int reverseCount = 0;
Node next = null;
for (Node node = tail; node != null; node = node.previous) {
if (node.next != next) return false;
next = node;
reverseCount++;
}
return next == head && reverseCount == size;
}
}
static void verify(String step, DoublyLinkedList values,
String expectedForward, String expectedBackward) {
String forward = values.forward();
String backward = values.backward();
boolean linksAgree = values.checkLinks();
if (!forward.equals(expectedForward)
|| !backward.equals(expectedBackward)
|| !linksAgree) {
throw new IllegalStateException("Check failed after " + step);
}
System.out.println("After " + step + ": forward=[" + forward
+ "], backward=[" + backward + "], links consistent=" + linksAgree);
}
public static void main(String[] args) {
DoublyLinkedList values = new DoublyLinkedList();
values.addFirst(10);
verify("insert at front", values, "10", "10");
values.addLast(30);
verify("insert at end", values, "10 <-> 30", "30 <-> 10");
values.insertAt(1, 20);
verify("insert in middle", values, "10 <-> 20 <-> 30", "30 <-> 20 <-> 10");
values.addFirst(5);
verify("another front insertion", values, "5 <-> 10 <-> 20 <-> 30", "30 <-> 20 <-> 10 <-> 5");
values.addLast(40);
verify("another end insertion", values, "5 <-> 10 <-> 20 <-> 30 <-> 40", "40 <-> 30 <-> 20 <-> 10 <-> 5");
values.removeAt(0);
verify("remove at front", values, "10 <-> 20 <-> 30 <-> 40", "40 <-> 30 <-> 20 <-> 10");
values.removeAt(1);
verify("remove in middle", values, "10 <-> 30 <-> 40", "40 <-> 30 <-> 10");
values.removeAt(2);
verify("remove at end", values, "10 <-> 30", "30 <-> 10");
values.removeAt(0);
verify("remove at front", values, "30", "30");
values.removeAt(0);
verify("remove final node", values, "", "");
LinkedList<String> names = new LinkedList<>();
names.add("Ada");
names.add("Linus");
ListIterator<String> iterator = names.listIterator(names.size());
ArrayList<String> reverse = new ArrayList<>();
while (iterator.hasPrevious()) reverse.add(iterator.previous());
System.out.println("Java LinkedList backward: " + reverse);
}
}
每次执行自定义链表操作后，verify 都会将预期的正向和反向序列与实际结果比较，并检查链接是否一致，然后打印当前状态。操作序列涵盖在开头、中间和末尾插入及移除节点，也包括链表从空变为只有一个节点，再恢复为空的过程。Node 类实现了自定义链表；Java 中单独的 LinkedList 示例则使用标准集合 API。代码块中的输出标签保留英文，打印内容包括正向和反向遍历结果以及链接一致性检查结果。
插入和删除 Node 节点
linkBetween 会指定新节点两侧的节点，并在插入发生于链表开头或末尾时更新头节点或尾节点。在链表中间插入时，两侧节点也都必须正确连接到新节点。如果只更新 next，反向遍历就可能出错。
删除时则反向执行相同的操作：将目标节点的前驱节点与后继节点连接起来；如果目标位于链表的一端，就更新 head 或 tail；最后清除被移除节点的引用。此实现中的 removeAt 会先查找索引，再移除已找到的节点。这一区别会影响性能：移除已知节点需要常数时间，而查找索引需要线性时间。nodeAt 会从距离较近的一端开始遍历，从而缩短遍历距离，但最坏情况下仍是线性时间。
在这个精简示例中，如果插入位置超出允许范围，insertAt 不会改变链表；如果无法移除节点，removeAt 会返回 -1。生产环境中的 API 应选择并说明适合调用者的错误报告策略。此版本允许在等于当前大小的位置插入，也就是追加元素。如果调用者需要按值移除节点，或移除已持有的节点，也可以添加相应方法或返回节点句柄。
遍历和测试链表
从 head 开始沿 next 正向遍历；从 tail 开始沿 previous 反向遍历。程序中的 forward 和 backward 方法分别格式化这两个方向的结果。checkLinks 会检查每一对相邻节点是否在两个方向上都正确连接，并确认访问到的节点数量与 size 相符。verify 会在每次修改后运行这些检查，并将两个方向的遍历结果与预期序列比较，从而发现过期的头节点或尾节点引用，以及未完成的链接更新。
示例的 main 方法演示了在开头、中间和末尾插入及移除节点。它先插入第一个节点，然后逐步移除节点，直到最后一个节点也被移除。每一步都会检查正向顺序、反向顺序和链接一致性，因此既测试了中间位置的修改，也测试了链表两端状态的变化。
何时使用双向链表
如果代码经常需要双向移动，或需要在已经找到目标节点后插入或移除节点，可以考虑使用双向链表。每个节点需要两个引用，因此比单向链表占用更多内存；按索引读取也比数组支持的列表慢，因为必须逐个遍历节点。若只需单向遍历，单向链表可以减少每个节点的存储开销；若经常按索引访问并希望节省空间，数组支持的 ArrayList 通常更合适。
如果 Java 的 LinkedList 提供的双端队列或列表操作符合需求，就使用它。若要学习指针关系，或需要集合未公开的节点级行为，则可以自行实现。无论采用哪种方式，都应根据目标位置是否已知来判断插入和删除的成本：更新少量链接开销较低，但查找位置仍需要与遍历距离成正比的时间。