Stacks

siva sankar — Tue, 21 Dec 2021 03:38:33 +0000

What is a stack?

A LIFO data structure

LIFO (Last in first out)

The last element added to the stack will be the first element removed from the stack.

Think about it like a pile of books. You can only add books on top, and you can only remove the book on top.

we are going to create stack that has only two methods

Push() : Method to add data to the stack
Pop() : Method to remove data from the stack

we can do this in different ways, In this article we are going to implement with JavaScript es6 classes.

JavaScript Stack Implementation

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

class Stack {

    constructor() {

        this.first = null;
        this.last = null;
        this.size = 0

    }

    push(val) {
        let newNode = new Node(val)
        if (!this.first) {
            this.first = newNode;
            this.last = newNode;
        }
        else {
            let temp = this.first;
            this.first = newNode;
            this.first.next = temp;
        }
        return ++this.size;
    }

    pop() {
        if (!this.first) return null;

        let temp = this.first;
        if (this.size === 1) {
            this.last = null;
        }
        this.first = this.first.next
        this.size--;
        return temp.value
    }
}


const stack = new Stack()

stack.push(1)
stack.push(2)
stack.push(3)
stack.pop()
stack.pop()
stack.pop()
stack.pop()

Where stacks are used

Managing function invocations
Undo/Redo
Routing (History Object)

BIG O of Stacks

Insertion - O(1)
Removal - O(1)
Searching - O(n)
Access - O(n)

Singly Linked List

siva sankar — Mon, 20 Dec 2021 07:43:44 +0000

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)

DEV Community: siva sankar