在 Java 中的 LinkeList 的开头插入一个新节点

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 开头的代码片段：

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 class 表示一个单节点，如下所示：

/**
* 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

假设您有以下链表：

2 -> 3 -> 4 -> 5

并且您想在开头插入一个值为1的节点。我们称这个节点为 newNode.

现在看这一行：newNode.setNext(head); 您正在使 newNode 的 next 值指向 head，在本例中指向节点2 的值。这是您的列表现在的样子：

1 -> 2 -> 3 -> 4 -> 5

但是，head 仍然指向值为 2 的节点，因此您必须通过使 head 指向值为 1，也就是 newNode。这就是 head = newNode; 行的作用。

Answer 2

当你的列表从右向左移动时，即 1 然后在插入新节点后它变成 2->1 然后在新插入后它变成 3->2->1，在这种情况下你需要只处理两件事：head（列表的第一个元素）和 temporary 下一个要插入的节点。这是伪代码：

`  while(you_want_to_insert_new_node)        //temporary is the node to be inserted freshly       
               {
                   Insert(temporary->data);  //Insert data in temporary node
                   temporary->next=head;
                   head=temporary;
               }
 `

当你的列表从左向右移动时，即 1->2 然后变成 1->2->3 等等，你需要注意三件事：head、current 节点和 temporary。这是伪代码：

` 
  current=head;
  while(you_want_to_insert_new_node)         //temporary is the node to be inserted freshly
                      {            
                                 Insert(temporary->data); //Insert data in temporary node
                                 current->next = temporary;
                                 current=temporary;
                      }

Answer 3

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

记住Java是按值传递；当你四处传递对象时，你并没有传递对象的值——你传递的是指向该对象的指针的值。 Is Java "pass-by-reference" or "pass-by-value"?

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

newNode.setNext(head)

head中的值是指向节点的指针。因此 setNext 函数根据按值传递接收指向节点的指针。它没有收到指向头的指针。

head = newNode;

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

您遇到了与 Java 的非常普遍的混淆，相信我，这是非常非常普遍的（因此我在上面引用的 SO 上获得了 2k 赞成票）。我希望这能解决您的主要困惑！

在 Java 中的 LinkeList 的开头插入一个新节点

Inserting a new Node at the beginning of a LinkeList in Java

java

linked-list

data-structures