Singly Linked List

What is a Singly Linked list?
A Singly linked list is a collection of nodes and each node has a value and a pointer to another node or null. The value can be any valid data type. You can see this illustrated in the diagram below.

The entry node in linked list is called Head and the last node is called Tail.

In Javascript a linked list can be implemented like this

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

    }
}

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


//This method used to push a value to end of the linked list
push(val){
   let newNode = new Node(val);
        if (!this.head) {
            this.head = newNode;
            this.tail=newNode;
        }
        else {
            this.tail.next = newNode;
            this.tail = newNode;
        }

        this.length++;
        return this;
}


//this method is used to remove an element from end of linked list.
 pop() {
        if(!this.head)return undefined

        let current = this.head;
        let previous = current;
        while (current.next) {
            previous = current;
            current = current.next

        }
        this.tail = previous
        previous.next = null;
        this.length = this.length - 1;
        if (this.length == 0) {
            this.tail = null
            this.head=null
        }
return this
    }


//this method is used to add a value to beginning of a list.
   unshift(val) {
        let newNode = new Node(val)
        if (!this.head) {
            this.head = newNode
            this.tail=newNode
        }
        else {
            let currentHead = this.head;
            newNode.next = currentHead;
            this.head=newNode
        }

        this.length++
        return this
    }



//this method is used to remove a value from beginning of a list
 shift() {

        if (!this.head) return undefined;
        if (this.length === 1) {
            this.head = null;
            this.tail = null

        }
        else {
            this.head = this.head.next;
        }

        this.length--;
return this;
    }


//this method is used to get a value from a particular position in list.

 get(position) {
        if (position < 0 ||position>=this.length) {
         return undefined
        }
        let index = 0;
        let currentHead = this.head;
        while (position!=index) {
            currentHead = currentHead.next;
            index++;
        }

return currentHead
    }


//this method is used to replace a value from a particular position in list.

   set(value, position) {

        let getValue = this.get(position)
        if (!getValue) return false;
        getValue.val=value
        return this
    }



//this method is user to insert an element in the list at a particular position.

insert(position, val) {
        if (position < 0 || position > this.length) {
            return undefined;
        }
        if (position === 0) {
            return this.unshift(val)
        }
        else if (position === this.length) {
          return  this.push(val)
        }
        let newNode = new Node(val)
        let previous = this.get(position - 1)
        if (!previous) return false;
        let nextEl = previous.next;
        newNode.next = nextEl;
        previous.next=newNode
        this.length++;

return this;
    }


//this method is used to remove a value from a particular position

remove(position) {

        if (position < 0 || position > this.length) {
            return undefined
        }

        if (position === 0) {
            return this.shift(val)
        }
        else if (position === this.length-1) {
            return this.pop(val)
        }
        let getEl = this.get(position-1)
        getEl.next = getEl.next.next;

        this.length--;
return this
    }

//this method is used to get the size of the list

size(){
return this.length
}

}

Advantages of singley linked list

• Insertions and Deletions can be done easily
• It does not need movement of elements for insertion and deletion unlike arrays.

Disadvantages of singley linked list

• Search operations are slow in linked lists. Unlike arrays, random access of data elements is not allowed. Nodes are accessed sequentially starting from the first node.

BIG O Notation

• Access O(n)
• Search O(n)
• Insertion O(1)
• Deletion O(1)