Java双向链表：高效删除指定索引节点教程

class Node<T> {
    T data; // 节点存储的数据
    Node<T> next; // 指向下一个节点的引用
    Node<T> previous; // 指向上一个节点的引用

    public Node(T data) {
        this.data = data;
        this.next = null;
        this.previous = null;
    }

    @Override
    public String toString() {
        return data.toString();
    }
}

public class DoublyLinkedList<T extends Comparable<T>> {
    protected Node<T> head; // 链表头节点
    protected Node<T> tail; // 链表尾节点
    int size = 0; // 链表当前大小

    public DoublyLinkedList() {
        this.head = null;
        this.tail = null;
    }

    /**
     * 向链表末尾添加一个新节点。
     * @param data 要添加的数据
     * @return 新创建的节点
     */
    public Node<T> append(T data) {
        Node<T> newNode = new Node<>(data);
        if (head == null) {
            // 链表为空，新节点既是头也是尾
            head = newNode;
            tail = newNode;
        } else {
            // 链表不为空，新节点添加到尾部
            newNode.previous = tail;
            tail.next = newNode;
            tail = newNode; // 更新尾节点
        }
        size++;
        return newNode;
    }

    /**
     * 辅助方法：将链表内容转换为字符串，便于调试。
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("Size[%d]: ", size));
        Node<T> current = head;
        while (current != null) {
            sb.append(current.data);
            if (current.next != null) {
                sb.append(" <-> ");
            }
            current = current.next;
        }
        return sb.toString();
    }

    // 删除方法将在下一节详细实现
    // public void delete(int location) { ... }
}

public void delete(int location) throws IllegalArgumentException {
    // 1. 验证链表状态和索引有效性
    if (head == null || location < 0 || location >= size) {
        throw new IllegalArgumentException("Invalid deletion location or empty list.");
    }

    // 根据删除位置分为三种情况处理
    if (location == 0) {
        // 情况一：删除头节点
        deleteHead();
    } else if (location == size - 1) {
        // 情况二：删除尾节点
        deleteTail();
    } else {
        // 情况三：删除中间节点
        deleteIntermediate(location);
    }
    size--; // 成功删除后，链表大小减一
}

private void deleteHead() {
    head = head.next; // 头节点指向下一个节点
    if (head != null) {
        head.previous = null; // 新头节点的previous为null
    } else {
        // 如果head变为null，说明原链表只有一个节点，删除后链表为空
        tail = null; // 尾节点也必须设为null
    }
}

private void deleteTail() {
    tail = tail.previous; // 尾节点指向上一个节点
    if (tail != null) {
        tail.next = null; // 新尾节点的next为null
    } else {
        // 如果tail变为null，说明原链表只有一个节点，删除后链表为空
        // 此分支在delete(int location)的逻辑下不会被触发，因为location == size - 1 且 size > 1
        // 但作为独立的辅助方法，考虑此情况是好的。
        head = null; // 头节点也必须设为null
    }
}

private void deleteIntermediate(int location) {
    Node<T> current = head;
    // 遍历到待删除节点的前一个节点
    for (int i = 0; i < location - 1; i++) {
        current = current.next;
    }

    // current 现在是待删除节点的前一个节点
    Node<T> nodeToDelete = current.next; // 待删除节点
    Node<T> nodeAfter = nodeToDelete.next; // 待删除节点后的节点

    current.next = nodeAfter; // 前一个节点的next指向待删除节点后的节点
    if (nodeAfter != null) {
        nodeAfter.previous = current; // 待删除节点后的节点的previous指向前一个节点
    }
    // 注意：如果nodeAfter为null，这意味着我们删除了原链表的倒数第二个节点，
    // 并且current成为了新的尾节点。然而，在这种情况下，deleteIntermediate
    // 不会直接更新tail。由于deleteIntermediate只处理中间节点，
    // 而删除倒数第二个节点严格来说不属于“中间节点”范畴，
    // 而是特殊情况，应该由deleteTail处理。
    // 但是，如果location == size - 2 (倒数第二个节点)，则它仍会进入此分支。
    // 在此情况下，current是新的tail，但tail变量没有更新。
    // 修正：如果nodeAfter为null，且此节点是倒数第二个节点，那么current就是新的tail。
    if (nodeAfter == null) {
        tail = current; // 更新tail为新的尾节点
    }
}