当我在中间引入循环时，单链表丢失的部分会发生什么？

Question

我创建了一个单链表，显示后是这样的：

19-->85-->50-->20-->33-->9-->1-->7-->null

我创建了一个方法，可以将节点添加到列表的任意位置。

public void add_node_any(int value , int position) {
    ListNode node = new ListNode(value);
    if (position == 1) {
        node.next = head;
        head = node;
    }
    else {
        ListNode previous = head;
        int count = 1;
        while (count < position - 1) {
            previous = previous.next;
            count++;
        }
        previous.next = node;
        node.next = previous.next;
    }
}

我试图将节点添加到第三个位置。

single.add_node_any(2, 3);

我意识到：

previous.next = node;
node.next = previous.next;

...正在创建一个循环。我还知道，由于这个循环，我无法访问 50 个以上的节点。所以我的问题是这些节点发生了什么？我看到声明说这些节点仍然是列表的一部分。它们只是无法访问。

如果这仍然是一部分，那是怎么发生的？我的意思是，虽然重复节点 (2) 和 50（循环中的下一个）之间没有连接，但如何保持与列表的连接？

完整代码

class SLL_implementation_Test_09_04 {
    private  listNode head;

    private  static class listNode {
        private int data;
        private listNode next;

        public listNode(int data) {
            this.data = data;
            this.next = null;
        }
    }   

    //Display the linked list
    public void Display() {
        listNode current = head;
        while (current != null) {
            System.out.print(current.data + "-->");
            current = current.next;      
        }   
        System.out.print("null"); 
    }

    //Display the length of the linked list
    public int SLL_length() {
        int count = 0;
        listNode current = head;
        while (current != null) {
            count++;
            current =current.next; 
        }   
        return count;
    }

    //Add new nodes | create a linked list from the beginning
    public void add_node_first(int value) {
        listNode newnode = new listNode(value);
        newnode.next = head;
        head = newnode;
    }

    //Add new nodes to the end of the linked list
    public void add_node_last(int value) {
        listNode newnode = new listNode(value);
        if (head == null) {
            head = newnode;
            return;
        }
        listNode current = head;
        while(current.next != null) {
            current = current.next;
        }
        current.next = newnode;
    }

    //Add a new node to a given possition
    public void add_node_any(int value, int position) {
        listNode node = new listNode(value);
        if (position == 1) {
            node.next = head;
            head = node;
        }
        else {
            listNode previous = head;
            int count = 1;
            while (count < position-1) {
                previous = previous.next;
                count++;
            }
            previous.next = node;
            node.next = previous.next;
        }
    }
}

在main方法中

    public static void main(String args[]) {
        SLL_implementation_Test_09_04 single = new SLL_implementation_Test_09_04();
        single.add_node_last(20);
        single.add_node_first(50);
        single.add_node_first(85);
        single.add_node_first(19); 
        single.add_node_last(33);
        single.add_node_last(9);
        single.add_node_last(1);
        single.add_node_last(7);
        single.add_node_any(2, 9);
        single.Display();
    }

Answer 1

我见过一些声明说这些节点仍然是列表的一部分。它们只是无法访问。

引用这些陈述会很有趣，但这是错误的。在代码为该属性分配其他内容之前 was

previous.next

的节点不再是列表的一部分。

如何才能保持与列表的连接？

你说得完全正确。 “链表”的定义包括节点在引用链中逐一链接。如果一个节点“只是不可访问”，那么它就不再位于该链中，并且根据定义，它不再是列表的一部分。

所以我的问题是这些节点发生了什么？

如果没有其他对原始列表断开部分的第一个节点的引用，则它可用于垃圾回收。这将级联到下一个节点，...等。这对于代码来说没有什么区别，无论它们是否已经被垃圾回收，代码都无法访问这些节点。

更正

更正是替换这个：

        previous.next = node;
        node.next = previous.next;

这样：

        listNode temp = previous.next;
        previous.next = node;
        node.next = temp;