Java实现双端链表为何出现末尾两元素无限重复输出问题

以下是带有main方法的Main类，用于实现双端链表的构建、节点删除与元素展示功能。

public class Main {
    Link first, last;

    public static void main(String args[]) {
    
        Main ob = new Main();

        Link arr[] = {
            new Link(1), new Link(2), new Link(3)
        };
        int len = 3;

        for(int i=0;i<len;i++)
            ob.insertFirst(arr[i]);
        System.out.print("Data in the list: ");
        while(ob.first!=null)
            System.out.print(ob.removeAndReturn()+", ");

        for(int i=0;i<len;i++)
            ob.insertLast(arr[i]);
        System.out.print("\nData in the list: ");
        while(ob.first!=null)
            System.out.print(ob.removeAndReturn()+", ");
    
    }

    void insertFirst(Link arg) {
        if(isEmpty())
            last = arg;
        arg.next = first;
        first = arg;
    }
    // removeAndReturn()方法返回节点存储的数据，同时将该节点从链表中移除
    Object removeAndReturn() {
        Object ret = null;
        try {
            ret = first.data;
            if(first.next==null)
                last = null;
            first = first.next;
        }catch(NullPointerException NPe) {
            System.out.println("You are referring to a null.\nLinked List is empty.");
        }
        return ret;
    }

    void insertLast(Link arg) {
        if(isEmpty())
            first = arg;
        else
            last.next = arg;
        last = arg;
    }

    boolean isEmpty() {
        return first==null;
    }
}


class Link {
    Object data;
    Link next;
    Link(Object data) {
        this.data = data;
    }
}

程序运行后得到如下输出：

Data in the list: 3, 2, 1, 
Data in the list: 1, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, ... {truncated}

输出结果中链表末尾两个元素出现无限重复的异常。尝试在调用ob.insertLast(arr[i])前将Link类型的first和last变量置空，仍得到相同的异常输出。

更新说明：

• 已移除Main类中除main(String args[])方法外其余所有方法签名的private关键字，原rmF()方法已重命名为removeAndReturn()。

问题出在复用Link对象时残留的next指针引用导致链表成环，和是否置空first/last指针没有关系：

1. 第一次执行头插操作后，arr里存储的三个Link对象的next指针已经被修改：3.next → 2、2.next →1、1.next → null
2. 后续调用removeAndReturn()遍历删除节点时，只是移动了链表的first、last指针，完全没有修改三个Link对象本身的next属性，这些引用关系一直残留在对象内存中
3. 第二次执行尾插时，直接复用了arr里的旧Link对象：
   • 插入arr[0]（值1）：链表头为1，此时1的next还是残留的null，逻辑正常
   • 插入arr[1]（值2）：1的next指向2，但2本身的next还残留着之前的引用指向1，此时已经出现临时环
   • 插入arr[2]（值3）：2的next被改为指向3，但3本身的next还残留着之前的引用指向2
4. 最终链表结构变成1 → 2 → 3 → 2 → 3 → 2...，2和3形成了循环引用，遍历的时候自然会无限重复输出这两个值。

置空first和last只是清空了Main对象对链表头尾的引用，arr数组还持有三个Link对象的强引用，对象本身的next属性值根本没被改动，自然解决不了问题。

在插入节点的方法里，先清空传入节点残留的next引用，再执行插入逻辑即可，修改两个插入方法：

void insertFirst(Link arg) {
    arg.next = null; // 插入前清空节点残留的引用
    if(isEmpty())
        last = arg;
    arg.next = first;
    first = arg;
}

void insertLast(Link arg) {
    arg.next = null; // 插入前清空节点残留的引用
    if(isEmpty())
        first = arg;
    else
        last.next = arg;
    last = arg;
}

修复后第二次插入的链表结构为1→2→3→null，遍历输出正常，结果为Data in the list: 1, 2, 3, 。

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