Link List in Es6 (Js)

Link list is the liner collection of data nodes. Each node contains the data + next (address of next node).  Head contains the reference of first node. Also , the next of last node contains null because there is no node after that.

Note : The principal benefit of a linked list over a conventional array is that the list elements can be easily inserted or removed without reallocation or reorganization of the entire structure because the data items need not be stored contiguously in memory or on disk, while restructuring an array at run-time is a much more expensive operation.

 

Link List

Let us perform some of basic operations in link list :

Add at first position : Now we want to add the node at first position. We have two scenarios with us

a)Suppose the link list is empty. It means the head contains null. So let us create a new node with following code :

var tmpNode=new Node(data);

Now, we can assign the newly created node to the head.

this.head = tmpNode;

b)Suppose we do have few nodes in the link list

so, whatever the node reference present inside the head of link list. We can assign it to the next of new node.

tmpNode.next=this.head;

and, then the head will contain the reference of new node created

this.head=tmpNode;


Add at last position : Now  we want to add the new node at last position. We do have to scenarios with us.

a)Suppose the link list is empty. It means that head contains the null. In this case we can assign the newly created node to the head. Because no node was created earlier so, the newly created node will be the last node

b)Suppose that we already have few node available. In this case we have to move to the last node by below code

var tmp=this.head; //assign head ref to tmp variable

while(tmp.next != null){

tmp=tmp.next;

Then , once we reach to the last node . We can assign the reference of newly created node to the next of last node.


 

Add at specific position : Now we want to add a new node after a specific position in the link list. In the addAfterSpecificIndex(post,data) function we are passing the position as a first argument. So inside the while loop we have applied the post decrement for the pos. On each decrement we are moving our tmp to the next node.

while(pos–){   // Iterate till pos became 0

tmp = tmp.next; // move to next node

}

Now , once we come to the particular position, we will apply following code to put new node after specific position

tmpNode.next = tmp.next;

// Assign the next of specific position node to the next of newly created node

tmp.next = tmpNode;

 

Delete at first position : Now we want to delete the node at first position. For this we have created a tmp variable . We have assigned head reference to it.
var tmp=this.head;
Then , we have to assign the next of the tmp node to the head of link list
this.head=tmp.next;
Finally , make the next of tmp to null

 

Delete at last position : Now we want to delete the node al last position. So, we have 2 scenarios with us.

a)Suppose there is only one node in the link list. Then it will be the last node tio be deleted

var tmp = this.head;

if(tmp.next==null){//If only one node
tmp.next=null; // So, now head contains null
}
b)Suppose , the list contains more then one node. We have to iterate the tmp variable to the 2nd last position. So, that we can make the next of second last node as null. Thus the last node gets deleted
while(tmp.next.next!=null){
tmp=tmp.next;
}
tmp.next=null;// Here tmp is at 2nd last position
deleteAtlastPosition(){

Delete At specific position : Now we want to delete the node at specific position. To de this we have to iterate to the node just previous to the specific position node.

var tmp = this.head;//assigned the head to tmp variable

var prePos = pos-1;

while(prePos–){

tmp=tmp.next;

}

tmp , now contains the  reference of node just previous to the specified position node.

tmp2 contains the reference of next node of current node.

var tmp2 = tmp.next;

current node next will contain the next of next node (tmp2)

tmp.next = tmp2.next;

Finally, target node next will became null. To disconnect the node to the list

tmp2.next=null;


Complete Code for link list :

Reverse a link list :

Input :

1->2->3->4->null

Output :

4->3->2->1->null

By Pankaj Kumar Agarwal

Leave a reply:

Your email address will not be published.