java - 在Java中的LinkedList的开头插入一个新节点

Question

我检查了我们在 SO 中的一些帖子。

Insert new node at the beginning of Linked-List

How do I insert a node at the beginning of a linked list?

并在 java 中实现了一个简单的 LinkedList，效果很好。

我无法理解的是如何将新节点添加到 LinkedList 的开头实际上是如何工作的。

以下是将节点添加到 LinkedList 开头的代码片段如下所示:

public class SinglyLinkedList
{
    //Private variable to keep tab of the HEAD of the linked list.
    private ListNode head;

    //Private variable to keep track of the node count in this singly linked list.
    private int length;
.
.
.
    /**
    * Insert a ListNode at the beginning of this List.
    */
    public synchronized void insertAtBegin(ListNode newNode)
    {
        //Set current head as the next of input ListNode
        newNode.setNext(head);

        //Set the input ListNode as the new head of this SinglyLinkedList
        head = newNode;

        //Increment the SinglyLinkedList length
        length++;
    }
.
.
.
}//End of class SinglyLinkedList

ListNode 类表示单个节点，如下所示:

/**
* Represents a Node of the Linked List.
*/
public class ListNode
{
    private ListNode next;  
    private int data;

    /**
    * Constructors
    */
        public ListNode()
        {
            next = null;
            data = Integer.MIN_VALUE;
        }
        public ListNode(int data)
        {
            next = null;
            this.data = data;
        }

    /**
    * Accessor methods.
    */  
        public int getData()
        {
            return this.data;
        }

        public void setData(int data)
        {
            this.data = data;
        }

        public ListNode getNext()
        {
            return next;
        }

        public void setNext(ListNode listNode)
        {
            this.next = listNode;
        }

        public String toString()
        {
            return Integer.toString(data);
        }

}//End of class ListNode

真正让我困惑的两行是:

//Set current head as the next of input ListNode
        newNode.setNext(head);
        //Set the input ListNode as the new head of this SinglyLinkedList
        head = newNode;

我越尝试分析这两行，我觉得它会创建一个循环引用结构，而不是插入“newNode”代替“head”。可能我不太明白 Java 引用是如何传递的。

是否有解释为什么上面两行不会以循环引用结束？

Answer 1

看来您从概念上理解 LinkedList 如何获取新的头节点。你的问题更多的是与Java本身相关。

请记住，Java 是按值传递的；当您传递对象时，您并不是在传递对象的值，而是在传递指向该对象的指针的值。 Is Java "pass-by-reference" or "pass-by-value"?

考虑到这一点，让我分解这两行。

newNode.setNext(head)

head 中的值是指向节点的指针。因此，setNext 函数按照值传递的方式接收指向节点的指针。它没有接收到指向 head 的指针。

head = newNode;

在这一行中，我们将 head 的 VALUE 重新分配为指向新创建的节点的指针。 newNode.next 中的值仍然是指向前一个头的指针。

您遇到了一个关于 Java 的非常常见的困惑，相信我，这是非常非常常见的(因此我上面提到的 SO 上有 2k 的赞成票)。我希望这能解决您困惑的主要原因!