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

Question

I have checked few posts that we have in SO.

Insert new node at the beginning of Linked-List

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

And implemented a simple LinkedList in java that works just fine.

What I can't get my head around is how adding a new Node to the beginning of the LinkedList would actually work.

Here is how my code snippet for adding a Node to the beginning of the LinkedList looks like:

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

The ListNode class represents a Single Node like so:

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

The 2 lines that really confuse me are:

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

The more I try to analyze these two lines, I feel it will create a circular reference structure instead of pushing in the "newNode" in place of "head". May be I don't quite understand how Java references are passed around.

Is there an explanation as to why the above two lines won't end up in a circular reference?

@Ayusman-Please accept the best answer, probably the highest upvoted one. Good day.:) — Am_I_Helpful, Jul 28 '15 at 17:52

Saad · Answer 1 · 2015-07-27T17:48:39.737

Imagine you have the following LinkedList:

2 -> 3 -> 4 -> 5

and you want to insert a node with a value of 1 at the beginning. Let's call this node newNode.

Now look at this line: newNode.setNext(head); You are making newNode's next value point to head, which in this case is pointing to the node with a value of 2. This is what your list looks like now:

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

However, head is still pointing to the node with the value of 2, so you have to fix that by making head point to the node with a value of 1, which is newNode. That is what the line head = newNode; does.

score 2 · Answer 2 · answered Jul 28 '15 at 01:42

When your list is moving from right to left, i.e. 1 then after new node insertion it becomes 2->1 then after fresh insertion it becomes 3->2->1, In this case you need to take care of two things only : head (the first element of the list) & temporary node which is to be inserted next. Here is the pseudo code for that:

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

When your list is moving from left to right, i.e 1->2 then it becomes 1->2->3 and so on, you need to take care of 3 things: head, the current node and the temporary. Here is the pseudo code for that:

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

score 2 · Accepted Answer · edited May 23 '17 at 10:26

It seems you understand conceptually how the LinkedList gets a new head node. Your question is more related to Java itself.

Remember that Java is pass-by-value; When you are passing objects around, you aren't passing the value of the object - you are passing the value of the pointer to that object. Is Java "pass-by-reference" or "pass-by-value"?

So with that in mind, let me break down those 2 lines.

newNode.setNext(head)

The value in head is a pointer to a node. So the setNext function is receiving, in accordance to pass-by-value, a pointer to a node. It is NOT receiving a pointer to head.

head = newNode;

in this line, we reassign head's VALUE to be a POINTER to the newly created node. The value in newNode.next is still a pointer to the previous head.

You are encountering a very common confusion with Java, and believe me it is VERY VERY common (hence the 2k upvotes on the SO I referenced above). I hope this addresses your main source of confusion!

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

3 Answers3