Javascript Algorithm: Singly Linked List

Singly Linked List is a data structure that contains a head, tail and length property. It consists of nodes (piece of data) , and each node are connected to each other. Simple Linked List item navigation is forward only.

There is no index, each node point to the next one

There is no index so if we want to access an item, we start from the beginning and ask for the next item. By analogy we can compare to a skyscraper that has no elevator, in an array there is an elevator and we can access any floor with the index, with linked list there is only stairs, we have to start from the beginning and go through each floors until the location wanted.

Creating a Linked list

Two steps are needed to create a linked list, first creating a node class then a SinglyLinkedList class that will utilized the node class.

1- Node class

To start we define a class that we will use to create each nodes. It contains. 2 properties: a piece of data and a reference to the next node.

class Node{
  constructor(val){
    this.val = val;     
    this.next = null;   
  }
}
// val is the piece of data
// next is the reference to the next node but at the beginning there  is nothing comping after so we set it to null.
let first = new Node("hi")
// first ==> Node {val: "hi", next: null}

2- Linked List class

Now that we have our node, we are going to create our linked list that utilize the node class and that connect to the next one. It has 3 properties head and tail that are pointers to the first and last item and a length.

class Node{
  constructor(val){
    this.val = val;     
    this.next = null;   
  }
}
class SinglyLinkedList {
  constructor(){
    this.head = null;     
    this.next = null;
    this.length = 0;   
  }
}
// The head and next property are set to null and the length to 0.
let list = new SinglyLinkedList()
// we created our linked 

Now we have created our Singly linked list, what we want to next is adding a bunch of methods to do specific actions.

Push action

Like .push() in an array, the push method add a new node to the end of the linked list.

let’s walk through each steps

1 // the function take a value and create a new node
push(val) {
  let newNode = new Node(val)
2 // if the linked list is empty(the head is null) we set the head and the tail to newly created node
if(!this.head)
      this.head = newNode
      this.tail = newNode 
}
3 // otherwise we take the tail and set the next property to the newNode and we update the tail to be the new value
  else {
       this.tail.next = newNode
       this.tail = newNode
   }
4 // Increment the length by one
   this.length ++
5 // return the new Linked List
    return this
  }
}

Shift action

The shift method remove a new node from the beginning of the linked list.

 // we define shift and does not take any argument
shift() {
1// If there are no nodes, return undefined
 if(!this.head) return undefined;
2 // store the item that is going to be deleted to a variable 
 let currentHead = this.head;
3// Set the head property to be the next value and decrement length
 this.head = currentHead.next;
 this.length--;
4 // if the linked list has just one item left we set tail to null
if(this.length === 0){
            this.tail = null;
        }
5 // return the new value of the node removed
return currentHead
 }
}

Here the basic logic of simply linked list and how some function works behind the scene , hope this give a better understanding and helps you to implement your own algorithms to work with this type of data structure.

Summary

-Linked list is just a collection of node
-Good for insertion and deletion
-3 properties : head, tail and length
-No Index
-Navigated only in one direction, from the first item to the next one

Bellow the complete linked list with the push and shift functions.

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

class SinglyLinkedList{
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    push(val){
        let 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;
        let current = this.head;
        let 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(){
        let(!this.head) return undefined;
        let currentHead = this.head;
        this.head = currentHead.next;
        this.length--;
        if(this.length === 0){
            this.tail = null;
        }
        return currentHead;
    }
}