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

问题描述

我已经检查了几篇关于SO的帖子。

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

我无法理解的是如何在LinkedList的开头添加一个新Node实际上是如何工作的。

这是将Node添加到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引用是如何传递的。

关于上述两行为什么不能最终以循环引用的方式有解释吗？

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

`  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 ，依此类推，您需要注意3件事： head ， 当前节点和临时节点。 这是伪代码：

` 
  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;
                      }

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

请记住，Java是按值传递的； 当您传递对象时，您没有传递对象的值，而是传递了指向该对象的指针的值。

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

newNode.setNext(head)

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

head = newNode;

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

您在使用Java时遇到了一个非常普遍的困惑，请相信我，这是非常普遍的（因此，我在上面引用的SO中有2k的票数）。 希望这能解决您的主要困惑！