Java 双向链表指定索引节点删除深度解析

1. 双向链表基础与泛型化

双向链表是一种数据结构，其中每个节点不仅包含数据，还包含指向其前一个节点（previous）和后一个节点（next）的引用。这使得链表可以双向遍历。为了提高代码的复用性和类型安全性，我们通常会使用泛型来定义双向链表及其节点。

1.1 Node 类结构

Node 类是双向链表的基本组成单元。它应该被设计为泛型，以存储任何类型的数据。

public 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();
    }
}

1.2 DoublyLinkedList 类结构

DoublyLinkedList 类管理着链表的整体结构，包括头节点（head）、尾节点（tail）和链表大小（size）。它也应是泛型的，并且为了使元素可比较（如果需要排序或特定查找），泛型类型 T 可以限定为实现 Comparable 接口。

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;
    }

    // 为了方便演示，添加一个toString方法
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("List Size [%d]: ", size));
        Node current = head;
        while (current != null) {
            sb.append(current.data);
            if (current.next != null) {
                sb.append(" <-> ");
            }
            current = current.next;
        }
        return sb.toString();
    }
}

2. 实现指定索引节点删除 (delete 方法)

删除双向链表中的节点比单向链表更为复杂，因为它需要同时维护前驱和后继节点的指针。此外，删除操作必须考虑多种边界条件，包括链表为空、删除头节点、删除尾节点、删除中间节点以及链表中只有一个节点的情况。

立即学习“Java免费学习笔记（深入）”；

ChatGPT Website Builder

ChatGPT网站生成器，AI对话快速生成网站

下载

2.1 参数校验

在执行任何删除操作之前，必须对传入的索引 location 进行严格的校验，确保其在有效范围内。

• 链表是否为空？
• location 是否为负数？
• location 是否超出链表实际大小？

    public void delete(int location) throws IllegalArgumentException {
        // 1. 参数校验：链表为空、索引越界
        if (head == null || location < 0 || location >= size) {
            throw new IllegalArgumentException("无效的删除位置或链表为空。");
        }
        // ... 后续删除逻辑
    }

2.2 分情况处理删除逻辑

为了确保 delete 方法的健壮性，我们需要根据待删除节点的位置进行分类讨论。

2.2.1 情况一：链表中只有一个节点

如果链表中只有一个节点，并且要删除它，那么 head 和 tail 都应该被设置为 null。

        // 2. 特殊情况：链表中只有一个节点
        if (size == 1) {
            head = null;
            tail = null;
        }

2.2.2 情况二：删除头节点 (location == 0 且 size > 1)

当链表包含多个节点，且要删除的是头节点时：

1. head 指针需要移动到原 head.next。
2. 新的 head 的 previous 指针应设置为 null。
3. 如果原链表只有两个节点，删除头节点后，新的 head 将成为唯一的节点，也即新的 tail。

        // 3. 删除头节点 (location == 0, 且 size > 1)
        else if (location == 0) {
            head