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;

addAtFirst(data){

var tmpNode=new Node(data);

if(this.head==null){//when the head contains null. It means we have no node present in the link list

this.head=tmpNode; //assign the newly created node to head

}

else //This block will execute when we have multiple nodes. And we want to add the node at first position

{

tmpNode.next=this.head; // first node ref passed to the next of new node

this.head=tmpNode; //Now, head contains the ref of new node

}

}

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.

addAtLast(data){
var tmpNode=newNode(data); //First create a new node

if(tmp==null){ //If the link list is empty
this.head=tmpNode; // Assign the ref of newly created node to head of link list
}
else{ // Now plan is to move to the last node

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

while(tmp.next != null){
tmp=tmp.next;
}

tmp.next=tmpNode; // assign the new node to the next of last node (tmp)
}
}

 

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;

addAfterSpecificIndex(pos,data){
//Suppose first node is at index 0
var tmpNode=newNode(data);
if(this.head==null){
console.log('List is empty');
}
else{
var tmp = this.head; // Assign head to the temporary variable tmp
while(pos--){   // Iterate till pos became 0
tmp = tmp.next; // move to next node
}
console.log('The current node is ',tmp);
tmpNode.next = tmp.next; // Assign the next of specific position node to the next of newly created node
tmp.next = tmpNode; // Again assign new node to the next of specific position node
}
}

 

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
deleteAtFirstPosition(){
if(this.head==null){
console.log('The list is empty');
}
else{
var tmp=this.head;
this.head=tmp.next;
tmp.next=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(){
if(this.head==null){//Suppose link list is empty
console.log('The list is empty');
}
else{//Suppose lint list is not empty
var tmp = this.head; // Assign head to tmp variable
if(tmp.next==null){//If only one node
tmp.next=null;
}
else{//If more then one node
while(tmp.next.next!=null){
tmp=tmp.next;
}
tmp.next=null;
}
}
}

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;

deleteAtSpecificPosition(pos){
var tmp = this.head;
var prePos = pos-1;
while(prePos--){
tmp=tmp.next;
}
var tmp2 = tmp.next; // tmp2 is the node to be deleted
tmp.next = tmp2.next;
tmp2.next=null;
console.log("The node at specific position is ",tmp)
}

Complete Code for link list :

<html>
<script>
//Es6
class Node{
constructor(data){
this.data = data;
this.next = null;
}
}
//node means a varibale that contacins the data+next
class LinkList{
constructor(){
this.head=null;
}

addAtFirst(data){
vartmpNode=newNode(data);
if(this.head==null){
this.head=tmpNode;
}
else{
tmpNode.next=this.head;
this.head=tmpNode;
}
}

addAfterSpecificIndex(pos,data){
//Suppose first node is at index 0
vartmpNode=newNode(data);
if(this.head==null){
console.log('List is empty');
}
else{
var tmp = this.head;
while(pos--){
tmp = tmp.next;
}
console.log('The current node is ',tmp);
tmpNode.next = tmp.next;
tmp.next = tmpNode;
}
}

addAtLast(data){
vartmpNode=newNode(data);
vartmp=this.head;
if(tmp==null){
this.head=tmpNode;
}
else{

while(tmp.next!=null){
tmp=tmp.next;
}
tmp.next=tmpNode;
}
}

traverse(){
vartmp=this.head;
if(tmp!=null){

while(tmp.next!=null){
console.log("==> ",tmp.data)
tmp=tmp.next;
}
console.log("==> ",tmp.data)
}
else{
console.log('List is empty')
}
}

deleteAtFirstPosition(){
if(this.head==null){
console.log('The list is empty');
}
else{
vartmp=this.head;
this.head=tmp.next;
tmp.next=null;
}
}

deleteAtSpecificPosition(pos){
var tmp = this.head;
var prePos = pos-1;
while(prePos--){
tmp=tmp.next;
}
var tmp2 = tmp.next;
tmp.next = tmp2.next;
tmp2.next=null;
console.log("The node at specific position is ",tmp)
}

deleteAtlastPosition(){
if(this.head==null){
console.log('The list is empty');
}
else{
var tmp = this.head;

if(tmp.next==null){//If only one node
tmp.next=null;
}
else{//If more then one node
while(tmp.next.next!=null){
tmp=tmp.next;
}
tmp.next=null;
}
}
}


}

var ll = new LinkList();
ll.addAtFirst(1000);
ll.addAtFirst(3000);
ll.addAtFirst(7000);
ll.addAtFirst(17000);
ll.addAtLast(111)
ll.addAtLast(222)
ll.addAtFirst(777)
ll.addAfterSpecificIndex(2,6000);
// ll.deleteAtlastPosition();
ll.deleteAtSpecificPosition(3);
ll.traverse();

</script>
</html>

Reverse a link list :

Input :

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

Output :

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

reverse(){
varnext=null;
varpre=null;
varcurr=this.head;
while(curr!=null){
next=curr.next;
curr.next=pre;
pre=curr;
curr=next;
}
this.head=pre;
}

By Pankaj Kumar Agarwal

Leave a reply:

Your email address will not be published.