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

class Student implements Comparable<Student> {
    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);
    }
}

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

    // ... delete 方法将在这里实现 ...

    /**
     * 辅助方法：将链表内容转换为字符串，便于可视化
     */
    @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);
            sb.append(" <-> "); // 使用 <-> 表示双向链接
            current = current.next;
        }
        if (sb.length() > "Size[0]: ".length()) { // 移除最后一个 <->
            sb.setLength(sb.length() - 5); 
        }
        return sb.toString();
    }
}

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<T> current = head;
        // 遍历到要删除节点的前一个节点
        for (int i = 0; i < location - 1; i++) {
            current = current.next;
        }
        // current 现在是目标节点的前一个节点
        Node<T> nodeToDelete = current.next;
        Node<T> nextNode = nodeToDelete.next;

        current.next = nextNode; // 前一个节点的next指向目标节点的next
        if (nextNode != null) {
            nextNode.previous = current; // 目标节点的next（如果存在）的previous指向前一个节点
        }
    }
    size--; // 链表大小减一
}

    public static void main(String[] args) {
        DoublyLinkedList<Student> 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
    }
}