How head.next is changed in singly linkedlist

1
votes

I have a big confusion in the simple singly linked list such as : in java.

node class :

public class node {

    public int data;
    public node next;

    public node(int data , node next) {
       this.data = data;
       this.next = next; 
    }
}

linked list class :

public linked list{

    public node first;
    public node last;

    public void add(int data){

        node x = new node(data,null);

        if( first == null ) { first= x; }
        else { last.next = x; }
        last = x;

    }
}

Here the big confusion , if the linked list is empty and I am trying to add new node for example : add(1);

The data of first node will be 1 and the next of first node will be null and also the data of last node will be 1 and the next of last node will be null

Now if I added a new node for example : add(2);

The data of last node will be 2 and the next of last node will be null and the data of first node will still 1 but the next of first node will be the tail, how this is happening ?

How head.next is changed in singly linkedlist ?

1
javaalgorithmoopdata-structureslinked-list
I believe your confusion will be cleared after understand how pointer works. - Roy Lee
indeed , the problem is solved . thank you - Logarithm Man
if that's what you're looking for, you may mark as "the answer". :) Welcome to SO. - Roy Lee
for sure , i am sorry . i am new member in stacoverflow - Logarithm Man

1 Answers

1
votes

how head.next is changed in singly linkedlist ?

Short answer: Because initially both first and last are pointing to the same node, last.next = x indirectly causes first.next = x.

Long answer:

The heart of it is object reference (pointer).

To understand why it changed, first you have to understand how pointer works in Java, a very high level language where you are hidden from all the nasty yet tedious memory manipulations.

tldr; I would refer you to watch this epic video that talks about pointer, Binky Pointer Video.

How Pointer works in Java

1. Memory allocation:

Statement below allocates new memories to hold node values(data & next). x is now holding the address value, i.e: 0x1ACD to actual node value. In other word, x is a node pointer.

  node x = new node(data,null); //0x1ACD

2. Pointer Dereferencing:

In order to access the actual node values, we need to dereference the address value. Pointer dereferencing happens when you access properties in Object, i.e: node.Next. The following statement dereference last and the object assignment copies the address value in x to next(property in last).

  last.next = x;

3. Object assignments:

Due to internal Java design (memory efficiency), instead of cloning the entire node value(in real world, it could be huge), object assignments copy only address value.

first and last now holds the same address value as x, which is address to actual node values.

public void add(int data){
    ...
    first = x; 
    last = x;
    ...
}

You may ask what is so great about this? Well, take the following example:

public void add(int data){
    ...
    first = x; 
    last = x;
    last.next = new node(123,null);
    ...
}

Note that now, last.next == first.next. Changing of node value via last also appears to modify first, because both of them are pointing to the same node values.

This is the complete answer to how head.next is changed in singly linkedlist ?

References:

  1. https://softwareengineering.stackexchange.com/questions/207196/do-pointers-really-exist-in-java
  2. https://softwareengineering.stackexchange.com/questions/141834/how-is-a-java-reference-different-from-a-c-pointer

Illustrations:

Step 1: When we add(1) to an empty list:

public void add(int data) {
    ...
    first= x; 
    ...
    last = x;
    ...
} 

// after:
   [1] <- first, last           // first and last now pointing to the same `node:x`.  
    |
   [/] <- first.next, last.next // first.next, last.next pointing to null.

Step 2: Now, when we add(2) to the previous list(non-empty):

// before:
   [1] <- first, last          
    |
   [/] <- first.next, last.next // first.next, last.next pointing to null.

public void add(int data) {
    ...
    // technically, since first and last pointing to the same node[1],
    // x actually being assigned to both first.next and last.next.
    last.next= x; 
    ...
    last = x;     // update last from previous-x to current-x.
    ...
} 

// after:
   [1] <- first
    |
   [2] <- last      // first.next, last is pointing to the new `node:x`.
    |
   [/] <- last.next // last.next to null.

Step 3 and etc: Now, let's add(3) or subsequent values to the list(non-empty):

// before:
   [1] <- first
    |
   [2] <- last      
    |
   [/] <- last.next // last.next to null.

public void add(int data) {
    ...
    last.next= x; // access previous-x and assign x to previous-x's next.
    ...
    last = x;     // update last from previous-x to current-x.
    ...
} 

// after:
   [1] <- first
    |
   [2]         
    |
   [3] <- last      // last is pointing to the new `node:x`. 
    |
   [/] <- last.next // last.next to null.

Note:

  • first always pointing to first node in list.

  • last always pointing to last node in list.

  • last.next is always pointing to null. Via Add(), a new node is always appended to the end of the list via assignment to last.next.