Java LinkedList实现问题：deleteLast返回尾元素但未实际删除

问题根源 #

你的deleteLast()方法失效的核心原因是**insertFirst()方法中size被错误累加了两次**，导致size值远大于实际链表元素数量：

public void insertFirst(int value){
    Node node = new Node(value);
    node.next = head;
    head = node;

    if(tail==null){
        tail=head;
        size+=1; // 第一次累加
    }

    size+=1; // 第二次累加
}

当插入第一个元素时，tail为空，size会被加两次（从0变成2），后续每次调用insertLast()都会继续错误累加size。最终size值与实际元素数量不符，deleteLast()中调用get(size-2)时，获取到的不是真正的倒数第二个节点，而是原尾节点，导致tail重新指向自己，删除操作无效。

另外insert()方法还存在逻辑错误：当index==0时，错误调用了insertLast()，应该调用insertFirst()。

修复方案 #

1. 修正insertFirst()的size计算：移除if块内的size+=1，只保留一次全局累加：

public void insertFirst(int value){
    Node node = new Node(value);
    node.next = head;
    head = node;

    if(tail==null){
        tail=head;
    }
    size += 1; // 仅一次累加
}

2. 修正insert()方法的索引0逻辑：

public void insert(int value, int index){
    if(index==0){
        insertFirst(value); // 替换为insertFirst
        return;
    }
    if(index==size){
        insertLast(value);
        return;
    }
    Node temp = head;
    for (int i = 1; i < index; i++) {
        temp = temp.next;
    }
    Node node = new Node(value, temp.next);
    temp.next = node;

    size+=1;
}

修复后完整代码 #

public class LL {

    public Node head;
    public Node tail;
    public int size;
    public LL(){
        this.size = 0;
    }

    public void insertFirst(int value){
        Node node = new Node(value);
        node.next = head;
        head = node;

        if(tail==null){
            tail=head;
        }
        size += 1;
    }

    public void insertLast(int value){
        if(tail==null) {
            insertFirst(value);
            return;
        }
        Node node = new Node(value);
        tail.next = node;
        tail = node;

        size+=1;
    }

    public void display(){
        Node temp = head;
        while(temp!=null){
            System.out.print(temp.value + " -> ");
            temp = temp.next;
        }
        System.out.println("END");
    }

    public void insert(int value, int index){
        if(index==0){
            insertFirst(value);
            return;
        }
        if(index==size){
            insertLast(value);
            return;
        }
        Node temp = head;
        for (int i = 1; i < index; i++) {
            temp = temp.next;
        }
        Node node = new Node(value, temp.next);
        temp.next = node;

        size+=1;
    }

    public int deleteLast(){
        if (size<=1){
            return deleteFirst();
        }
        Node secondLast = get(size-2);
        int val = tail.value;
        tail = secondLast;
        tail.next = null;
        size-=1;
        return val;
    }

    public Node get(int index){
        Node node = head;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }

    public int deleteFirst(){
        int num = head.value;
        head = head.next;
        if(head==null){
            tail=null;
        }
        size-=1;
        return num;
    }

    public class Node{
        private int value;
        private Node next;

        public Node(int value) {
            this.value = value;
        }
        public Node(int value, Node next){
            this.value = value;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        LL linkedList = new LL();

        linkedList.insertLast(1);
        linkedList.insertLast(2);
        linkedList.insertLast(3);

        System.out.println("Original list:");
        linkedList.display();

        int deletedValue = linkedList.deleteLast();
        System.out.println("Deleted value: " + deletedValue);

        System.out.println("List after deleting last element:");
        linkedList.display();
    }
}

修复后运行输出 #

Original list:
1 -> 2 -> 3 -> END
Deleted value: 3
List after deleting last element:
1 -> 2 -> END

内容的提问来源于stack exchange，提问作者Rohan Dsouza