linked list javascript es6

linked list javascript es6

Linked lists are important data structures. My goal is to provide a detailed explanation of how to create a Single Linked List javascript es6 and explain the logic of each line of code.

linked list operations

Below are the methods we will create and a pseudocode for each method will be provided.

  • Swap the head and tail.
  • Create a variable called next node.
  • Create a variable called previous.
  • Create a variable called node and initialize it to the head property.
  • Loop through the list.
  • Set next to be the next property of whatever node is.
  • Set the next property of the node to whatever prev is.
  • Set prev to be the value of the node variable.
  • Set the node variable to be the value of the next variable.

linked list javascript es6 Structure

Two classes are created, Node class and SingleLinkedList class.

class Node{
  constructor(val){
      this.val = val;
      this.next = null;
  }
}


class SingleLinkedList{
  constructor(){
      this.head = null;
      this.tail = null;
      this.length = 0;
  }
}

Push pseudocode

  • This method accept a value.
  • Create a new node using the value passed to the method.
  • If their is no head property on the list, set the head and tail to be the new Node.
  • If there is head property on the list, set the next property on the tail to be the new node and set thetail property on the list to the new node created.
  • Increment the length by one.
  • Return the linked list.

Push implementation

push(val){
    var newNode = new Node(val);
    if(!this.head){
        this.head = newNode;
        this.tail = this.head;
    }else{
        this.tail.next = newNode;
        this.tail = newNode
    }
    this.length++;
    return this;
}

Push Method Testing.

var list = new SingleLinkedList();
console.log(list)  // SingleLinkedList {head: null, tail: null, length: 0}

list.push('swagasoft')
/*SingleLinkedList {head: Node, tail: Node, length: 1}
head: Node {val: "swagasoft", next: null}
length: 1
tail: Node {val: "swagasoft", next: null}
__proto__: Object */


list.push('again')
/* SingleLinkedList {head: Node, tail: Node, length: 2}
head: Node {val: "swagasoft", next: Node}
length: 2
tail: Node {val: "again", next: null}
__proto__: Object */
// The previous head is now the new tail while the last push is now the head.

Pop Pseudocode

  • If there is no Node in the head, return undefined
  • Loop through the list until you find the tail.
  • Set the next property of the second to the last Node to be null.
  • Set the tail to be second to the last node.
  • Decrement length by one.
  • return the value of the node removed.

Pop Method implementation

pop(){
    if(!this.head) return undefined;
    var current = this.head
    var newTail = current;
    while(current.next){
        newTail = current;
        current = current.next;
    }
    this.tail = newTail;  
    this.tail.next = null;
    this.length--;
    if(this.length === 0){
        this.head = null
        this.tail = null
    }
    return current;
}

Pop Method Testing

var list = new SingleLinkedList();
console.log(list)  // SingleLinkedList {head: null, tail: null, length: 0}  // default head and tail is null
// undefined

list.push(1)
/* SingleLinkedList {head: Node, tail: Node, length: 1}
 head: Node {val: 1, next: null}
 length: 1
 tail: Node {val: 1, next: null}
 __proto__: Object */


list.push(2)
/*
SingleLinkedList {head: Node, tail: Node, length: 2}
head: Node {val: 1, next: Node}
length: 2
tail: Node {val: 2, next: null}
__proto__: Object
*/

list.pop()
// Node {val: 2, next: null}
// The last element was popped out from the list.

Shift Psuedocode

Remove a new node from the linked list.

  • If there is no Node, return undefiend
  • Store the current head in a variable
  • Set the head property to be the current head next property
  • Decrement the length by one.
  • Return the value removed.
shift(){
if(!this.head) return undefined;
var currentHead = this.head;
this.head = currentHead.next;
this.length--;
if(this.length === 0){
  this.tail = null;
}
return currentHead;
}

You can do a test calling this method just I did in the example above.

Unshift Pseudocode

Adding a new node at the beginning of the linked list.

  • create a new Node using the value passed to the method.
  • If there is no head property on the list,Set the head and tail to be the newly created Node.
  • Else set the newly created Node’s next property to be the current head property on the list.
  • Increment the lenght by one.
  • return the linked list.
unShift(val){
var newNode = new Node(val);
if(!this.head){
  this.head = newNode;
  this.tail = newNode;
}else{
  newNode.next = this.head;
  this.head = newNode;
}
  
  this.length++;
  return this;
}

Get Pseudocode

Retrieving a Node by its position.

  • The method should accept an index.
  • If the index is less than zero or greater than or equal to length of the list return null.
  • Loop through the list until you reach the index and return the Node at the specific.
unShift(val){
var newNode = new Node(val);
if(!this.head){
  this.head = newNode;
  this.tail = newNode;
}else{
  newNode.next = this.head;
  this.head = newNode;
}
  
  this.length++;
  return this;
}

Set Pseudocode

Change the value of a Node at a specific index.

  • Accept a value and an index.
  • Use the GET method to find the given index.
  • If the Node is not found return false.
  • If the Node is found , set the ue he found Node to be the value passed ino the method.
  • Reurn true.
set(val, index){
var foundNode = this.get(index);
if (foundNode){
  foundNode.val =val;
  return true;
}
return false;
}

Insert Pseudocode

Insert a Node at a given index.

  • If the index isss than zero or greater than the lenght, return false.
  • If the index is equal to the lenght, push a new Node to the end of the list.
  • If the index zero push a new Node to the start of the list.
  • Otherwise use the GET method to access the Node at index- 1.
  • Set the next property of that Node to be the new Node.
  • Set the next property on the new node to be the previous next
  • Increment the length by one.
  • return true.
insert(index,val){
if(index < 0 || index > this.length) return false;

if(index === this.length) {
  this.push(val);
  return true;
};

if(index === 0){
  return !!this.unShift(val);
}else{
  var newNode = new Node(val);
  var previous = this.get(index - 1);
  var temp = previous.next;
  newNode.next = temp;
  this.length++;
  return true;
}

}

Remove Pseudocode

Remove a node at a specific position

  • if the index is less than zero or greater than the length, return undefined.
  • if the index is the same as the length – 1, use the pop method.
  • if the index is zero, use the shift method.
  • otherwise using the get method, access the node at the index -1.
  • set the next node property on that node to be the next of the next node.
  • decrement the lenght.
  • return the value of the node removed.
remove(index){
if(index < 0 || index >= this.length) return undefined;
if( index === 0 ) return this.shift();
if(index === this.length - 1) return this.pop();

var previousNode = this.get(index - 1);
if(!this.head?.next){
this.pop();
}
var removedNode = previousNode.next;
previousNode.next = removedNode.next;
this.length--;
return removedNode;
}

Reverse Pseudocode

Reverse the linked list in a place so that the head becomes the tail and the tail becomes the head.

  • Swap the head and tail.
  • Create a variable called next node.
  • Create a variable called previous.
  • Create a variable called node and initialize it to the head property.
  • Loop through the list.
  • Set next to be the next property of whatever node is.
  • Set the next property of the node to whatever prev is.
  • Set prev to be the value of the node variable.
  • Set the node variable to be the value of the next variable.
reverse(){
var node = this.head;
this.head =  this.tail;
this.tail = node;

var next, prev = null;
for(let i = 0; i < this.length; i++){
next = node.next;
node.next =  prev;
prev = node;
node =  next; 
}
return this;
}

Conclussion

I implemented the linked list operator:

  • Pop: This method removes the last Node in the List.
  • Shift: Remove the first Node in the list
  • .Unshift: Add a new Node to the beginning of the list.
  • Get: retrieve a Node by its position.
  • Set: change the value of a Node based on its position
  • Insert: insert a value at a specific position.
  • Remove: remove a node from the list at a specific position.
  • Reverse: reverse the list so the head becomes the tail and the tail becomes the head.
  • The full linked list javascript es6

    class Node{
      constructor(val){
          this.val = val;
          this.next = null;
      }
    }
    
    
    // var first = new Node('hi')
    // first.next =new Node('simon')
    // first.next.next = new Node('good')
    class SingleLinkedList{
      constructor(){
          this.head = null;
          this.tail = null;
          this.length = 0;
      }
    
    push(val){
        var newNode = new Node(val);
        if(!this.head){
            this.head = newNode;
            this.tail = this.head;
        }else{
            this.tail.next = newNode;
            this.tail = newNode
        }
        this.length++;
        return this;
    }
    
    
    pop(){
        if(!this.head) return undefined;
        var current = this.head
        var newTail = current;
        while(current.next){
            newTail = current;
            current = current.next;
        }
        this.tail = newTail;  
        this.tail.next = null;
        this.length--;
        if(this.length === 0){
            this.head = null
            this.tail = null
        }
        return current;
    }
    
    
    shift(){
    if(!this.head) return undefined;
    var currentHead = this.head;
    this.head = currentHead.next;
    this.length--;
    if(this.length === 0){
      this.tail = null;
    }
    return currentHead;
    }
    
    
    
    unShift(val){
    var newNode = new Node(val);
    if(!this.head){
      this.head = newNode;
      this.tail = newNode;
    }else{
      newNode.next = this.head;
      this.head = newNode;
    }
      
      this.length++;
      return this;
    }
    
    
    
    get(index){
    if(index < 0 || index >= this.length) return null;
    
    var counter = 0;
    var currentVal = this.head;
    while(counter !== index){
      currentVal = currentVal.next;;
      counter++;
    }
    return currentVal;
    
    }
    
    
    
    set(val, index){
    var foundNode = this.get(index);
    if (foundNode){
      foundNode.val =val;
      return true;
    }
    return false;
    }
    
    
    
    insert(index,val){
    if(index < 0 || index > this.length) return false;
    
    if(index === this.length) {
      this.push(val);
      return true;
    };
    
    if(index === 0){
      return !!this.unShift(val);
    }else{
      var newNode = new Node(val);
      var previous = this.get(index - 1);
      var temp = previous.next;
      newNode.next = temp;
      this.length++;
      return true;
    }
    
    }
    
    
    remove(index){
    if(index < 0 || index >= this.length) return undefined;
    if( index === 0 ) return this.shift();
    if(index === this.length - 1) return this.pop();
    
    var previousNode = this.get(index - 1);
    if(!this.head?.next){
    this.pop();
    }
    var removedNode = previousNode.next;
    previousNode.next = removedNode.next;
    this.length--;
    return removedNode;
    }
    
    reverse(){
    var node = this.head;
    this.head =  this.tail;
    this.tail = node;
    
    var next, prev = null;
    for(let i = 0; i < this.length; i++){
    next = node.next;
    node.next =  prev;
    prev = node;
    node =  next; 
    }
    return this;
    }
    
    }
    
    
    var list = new SingleLinkedList();
    

    You can learn more from the following link

    Leave a Reply

    Your email address will not be published. Required fields are marked *