Java双向链表：实现高效的按索引删除节点操作
本文详细讲解了如何在Java中为双向链表实现按索引删除节点的操作。教程涵盖了泛型设计、节点结构、参数校验、以及针对头节点、尾节点和中间节点的删除逻辑，并强调了维护链表head、tail和size等状态的准确性，确保了删除操作的健壮性和正确性。
1. 双向链表节点与泛型设计
在实现双向链表时，为了提高代码的复用性和灵活性，我们通常会采用泛型设计。一个双向链表的节点不仅包含数据，还需要指向前一个节点和后一个节点的引用。
Node 类结构：
class Node{ T data; // 存储节点数据 Node next; // 指向下一个节点 Node previous; // 指向前一个节点 public Node(T data) { this.data = data; this.next = null; this.previous = null; } @Override public String toString() { return data.toString(); } }
这里，Node
Student 示例类：
class Student implements Comparable{ private static int counter; private int id; public Student() { id = ++counter; } @Override public int compareTo(Student o) { return id - o.id; } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null || getClass() != obj.getClass()) return false; Student other = (Student) obj; return id == other.id; } @Override public int hashCode() { return id; } @Override public String toString() { return String.format("%d", id); } }
Student 类实现了 Comparable
2. 双向链表基础结构
DoublyLinkedList 类是双向链表的管理核心，它维护着链表的头部 (head)、尾部 (tail) 以及当前链表的大小 (size)。
public class DoublyLinkedList> { protected Node head; protected Node tail; int size = 0; public DoublyLinkedList() { this.head = null; this.tail = null; } /** * 在链表末尾添加一个新节点 * @param data 要添加的数据 * @return 新添加的节点 */ public Node append(T data) { Node newNode = new Node<>(data); if (head == null) { // 链表为空时 head = newNode; tail = newNode; } else { // 链表不为空时 newNode.previous = tail; tail.next = newNode; tail = newNode; } size++; return newNode; } // ... delete 方法将在这里实现 ... /** * 辅助方法：将链表内容转换为字符串，便于可视化 */ @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append(String.format("Size[%d]: ", size)); Node current = head; while (current != null) { sb.append(current); sb.append(" <-> "); // 使用 <-> 表示双向链接 current = current.next; } if (sb.length() > "Size[0]: ".length()) { // 移除最后一个 <-> sb.setLength(sb.length() - 5); } return sb.toString(); } }
append 方法负责在链表末尾添加新节点，并正确更新 head、tail 和 size。toString 方法则提供了一个方便的链表内容展示方式。
3. 实现按索引删除节点 (delete方法)
删除操作是链表管理中较为复杂的部分，需要仔细处理各种边界条件和指针重定向。
public void delete(int location) throws IllegalArgumentException {
// 3.1 参数校验
// 检查索引是否合法：非负且小于链表大小
if (head == null || location < 0 || location >= size) {
throw new IllegalArgumentException("无效的索引或链表为空，无法删除节点。");
}
// 3.2 核心逻辑：分情况处理
if (location == 0) { // 情况一：删除头节点
head = head.next; // 头节点指向下一个节点
if (head != null) {
head.previous = null; // 新头节点的前驱设为null
} else { // 如果链表只有一个节点，删除后链表为空
tail = null;
}
} else if (location == size - 1) { // 情况二：删除尾节点
tail = tail.previous; // 尾节点指向前一个节点
if (tail != null) {
tail.next = null; // 新尾节点的后继设为null
} else { // 如果链表只有一个节点（此分支不会执行，因为location=0已处理）
head = null;
}
} else { // 情况三：删除中间节点
Node current = head;
// 遍历到要删除节点的前一个节点
for (int i = 0; i < location - 1; i++) {
current = current.next;
}
// current 现在是目标节点的前一个节点
Node nodeToDelete = current.next;
Node nextNode = nodeToDelete.next;
current.next = nextNode; // 前一个节点的next指向目标节点的next
if (nextNode != null) {
nextNode.previous = current; // 目标节点的next（如果存在）的previous指向前一个节点
}
}
size--; // 链表大小减一
} delete 方法详解：
- 3.1 参数校验： 首先，对传入的 location 参数进行严格校验。如果 location 小于 0 或大于等于链表当前 size，则表示索引无效，抛出 IllegalArgumentException。此外，如果链表本身为空 (head == null)，也无法执行删除操作。
-
3.2 核心逻辑：分情况处理
-
情况一：删除头节点 (location == 0)
- 将 head 指针直接移动到 head.next。
- 如果新的 head 不为 null，则将其 previous 指针设为 null。
- 特殊处理： 如果删除头节点后 head 变为 null（即原链表只有一个节点），则 tail 也必须设为 null，表示链表已空。
-
情况二：删除尾节点 (location == size - 1)
- 将 tail 指针移动到 tail.previous。
- 如果新的 tail 不为 null，则将其 next 指针设为 null。
- 此分支不会处理链表只剩一个节点的情况，因为 location == 0 已覆盖。
- 情况三：删除中间节点 (0
- 使用一个 current 指针从 head 开始遍历，直到找到要删除节点的前一个节点。
- 一旦找到 current (即 location - 1 处的节点)，我们就可以获取到 nodeToDelete = current.next 和 nextNode = nodeToDelete.next。
-
重定向
指针：- current.next = nextNode;：将 current 的 next 指针绕过 nodeToDelete，直接指向 nextNode。
- if (nextNode != null) { nextNode.previous = current; }：如果 nextNode 存在，则将其 previous 指针指向 current，完成双向链接的修复。
-
情况一：删除头节点 (location == 0)
- 3.3 链表大小更新： 无论哪种情况，只要成功删除了节点，size 都必须减 1。
指针：4. 辅助方法与示例
为了验证 delete 方法的正确性，我们可以添加一个 main 方法进行测试。
public static void main(String[] args) {
DoublyLinkedList dll = new DoublyLinkedList<>();
System.out.println("初始链表: " + dll);
// 添加节点
dll.append(new Student()); // 1
dll.append(new Student()); // 2
dll.append(new Student()); // 3
dll.append(new Student()); // 4
System.out.println("添加4个节点后: " + dll); // Size[4]: 1 <-> 2 <-> 3 <-> 4
// 测试删除操作
System.out.println("\n--- 测试删除操作 ---");
// 删除中间节点 (索引 1，即节点2)
dll.delete(1);
System.out.println("删除索引1的节点后: " + dll); // Size[3]: 1 <-> 3 <-> 4
// 删除头节点 (索引 0，即节点1)
dll.delete(0);
System.out.println("删除索引0的节点后: " + dll); // Size[2]: 3 <-> 4
// 删除尾节点 (索引 size-1，即节点4)
dll.delete(dll.size - 1);
System.out.println("删除尾节点后: " + dll); // Size[1]: 3
// 删除最后一个节点 (索引 0，即节点3)
dll.delete(0);
System.out.println("删除最后一个节点后: " + dll); // Size[0]:
// 尝试在空链表上删除
try {
dll.delete(0);
} catch (IllegalArgumentException e) {
System.out.println("尝试在空链表上删除（预期错误）: " + e.getMessage());
}
// 重新添加节点，测试删除倒数第二个节点
System.out.println("\n--- 测试删除倒数第二个节点 ---");
dll.append(new Student()); // 5
dll.append(new Student()); // 6
dll.append(new Student()); // 7
System.out.println("添加3个节点后: " + dll); // Size[3]: 5 <-> 6 <-> 7
dll.delete(1); // 删除索引1的节点 (即节点6)
System.out.println("删除索引1的节点后: " + dll); // Size[2]: 5 <-> 7
// 验证 tail 是否正确
System.out.println("当前 tail: " + (dll.tail != null ? dll.tail.data : "null")); // 应该是 7
}
} 5. 注意事项与总结
- 边界条件处理： 删除操作的复杂性主要体现在对边界条件（空链表、删除头节点、删除尾节点、链表只剩一个节点）的细致处理上。任何一个指针的错误指向都可能导致链表断裂或 NullPointerException。
- 指针重定向： 双向链表在删除节点时，不仅要更新被删除节点的前一个节点的 next 指针，还要更新被删除节点的后一个节点的 previous 指针。
- head 和 tail 的维护： 每次删除操作都可能影响 head 和 tail 指针，尤其是在删除头节点或尾节点，以及链表变为空时，必须确保这两个关键指针的正确性。
- size 的更新： 及时更新链表的 size 成员变量对于维护链表状态和进行有效参数校验至关重要。
- 泛型优势： 采用泛型设计使链表具有更好的通用性，能够存储和操作各种类型的数据。
通过上述详细的步骤和代码示例，我们可以实现一个健壮且高效的Java双向链表按索引删除节点的操作。理解并正确处理这些细节是掌握链表数据结构的关键。
