Implement stack using linked list

Posted on | by Prashant Yadav

Posted in , ,

Learn how to implement stack using linked list in javascript.

A stack is an ordered collection of data in which data is inserted in LIFO (Last In First Out) order. We will see how to implement it using a object based single linked list in javascript.

List of operations performed on stack

  • Push: Adds the item in the stack at the top.
  • Pop: Removes the top item from the stack and returns it.
  • Peek: Shows the top item from the stack.
  • toArray: Convert the stack to the array.
  • size: Returns the size of the stack.
  • isEmpty: Returns true if stack is empty, false other wise.
  • clear: Clears the stack.

Implementing stack using single linked list

We will see two different methods to implement stack using linked list in javascript.
1) Using function as a constructor.
2) Using class.

While implementing stack we will use length to keep track of the size of the stack and head to keep track of the list.

//Stack using linkedlist
function stackUsingLL(){
  //Node 
  let Node = function(elm){
    this.element = elm;
    this.next = null;
  }

  //To keep track of the size  
  let length = 0;
  
  //To keep track of the list
  let head = null;

  //Other methods go here
}

Push an item in the stack

As in the stack new item are added on the top, If the head is empty then the new node will be the first element, else we will make all the new node of the linked list to be the first node by assigning all the old nodes to the new node.

Push data in (stack using linked list) 

//Push data in the stack
  this.push = function(elm){
    //Create a new node
    let node = new Node(elm),
    current;
    
    //Add the new node at the top
    current = head;
    node.next = current;
    head = node;
    
    length++;
  }

Pop an item from the stack

To remove an item from the stack we can just make the head to point the very next element.

Pop an item (from the stack using linked list)

 //Pop the item from the stack
  this.pop = function(){
    let current = head;
    
    //If there is item then remove it 
    //and make the next element as the first
    if(current){
      let elm = current.element;
      current = current.next;
      head = current;
      length--;
      return elm;
    }
    
    return null;   
  }

Peek the top item in the stack

While peeking just return the first item in the list.

//Return the first element in the stack
  this.peek = function(){
    if(head){    
      return head.element;
    }

    return null;
  }

Converting stack to an array.

To convert the stack to an array, we can copy all the items to the array and return it.

//Convert the stack to an array
  this.toArray = function(){
    let arr = [];
    let current = head;
    while(current){
      arr.push(current.element);
      current = current.next;
    }
    
    return arr;
  }

Get the size of the stack

Return the length of the stack

//Return the size of the stack
  this.size = function(){
    return length;
  }

Check if stack is empty

//Check if stack is empty
  this.isEmpty = function(){
    return length === 0;
  }

Clear the stack

//Clear the stack
  this.clear = function(){
    head = null;
    length = 0;
  }

Complete code for stack using linked list

//Stack using linkedlist
function stackUsingLL(){
  //Node 
  let Node = function(elm){
    this.element = elm;
    this.next = null;
  }
  
  //To keep track of the size  
  let length = 0;
  
  //To keep track of the list
  let head = null;
  
  //Push data in the stack
  this.push = function(elm){
    //Create a new node
    let node = new Node(elm),
    current;
    
    //Add the new node at the top
    current = head;
    node.next = current;
    head = node;
    
    length++;
  }
  
  //Pop the item from the stack
  this.pop = function(){
    let current = head;
    
    //If there is item then remove it 
    //and make the next element as the first
    if(current){
      let elm = current.element;
      current = current.next;
      head = current;
      length--;
      return elm;
    }
    
    return null;   
  }
  
  //Return the first element in the stack
  this.peek = function(){    
    if(head){    
      return head.element;
    }

    return null;
  }
  
  //Convert the stack to an array
  this.toArray = function(){
    let arr = [];
    let current = head;
    while(current){
      arr.push(current.element);
      current = current.next;
    }
    
    return arr;
  }
  
  //Check if stack is empty
  this.isEmpty = function(){
    return length === 0;
  }
  
  //Return the size of the stack
  this.size = function(){
    return length;
  }
  
  //Clear the stack
  this.clear = function(){
    head = null;
    length = 0;
  }
  
}

 Input:
 let stack = new stackUsingLL();   //creating new instance of Stack
 stack.push(1);
 stack.push(2);
 stack.push(3);
 console.log(stack.peek());
 console.log(stack.isEmpty());
 console.log(stack.size());
 console.log(stack.pop());
 console.log(stack.toArray());
 console.log(stack.size());
 stack.clear();  //clear the stack
 console.log(stack.isEmpty());

 Output:
 3
 false
 3
 3
 [2, 1]
 2
 true

We can make the properties and methods private using closure and IIFE (Immediately Invoked function expression).

let stackUsingLL = (function(){
  
  //Stack using linkedlist
  return function stack(){
    //Node 
    let Node = function(elm){
      this.element = elm;
      this.next = null;
    }

    //To keep track of the size  
    let length = 0;

    //To keep track of the list
    let head = null;

    //Push data in the stack
    this.push = function(elm){
      //Create a new node
      let node = new Node(elm),
      current;

      //Add the new node at the top
      current = head;
      node.next = current;
      head = node;

      length++;
    }

    //Pop the item from the stack
    this.pop = function(){
      let current = head;

      //If there is item then remove it 
      //and make the next element as the first
      if(current){
        let elm = current.element;
        current = current.next;
        head = current;
        length--;
        return elm;
      }

      return null;   
    }

    //Return the first element in the stack
    this.peek = function(){    
      if(head){    
         return head.element;
      }

      return null;
    }

    //Convert the stack to an array
    this.toArray = function(){
      let arr = [];
      let current = head;
      while(current){
        arr.push(current.element);
        current = current.next;
      }

      return arr;
    }

    //Check if stack is empty
    this.isEmpty = function(){
      return length === 0;
    }

    //Return the size of the stack
    this.size = function(){
      return length;
    }

    //Clear the stack
    this.clear = function(){
      head = null;
      length = 0;
    }

  }
  
}());

Class based implementation of stack using linked list in javascript.

We will use two different classes.
1) To create the Nodes.

//Node
class Node {
  constructor(elm){
    this.element = elm;
    this.next = null;
  }
}

2) To implement the stack.

class stackUsingLL {
  constructor(){
    this.length = 0;
    this.head = null;
  }
  
   //Push data in the stack
   push = (elm) => {
    //Create a new node
    let node = new Node(elm),
    current;
    
    //Add the new node at the top
    current = this.head;
    node.next = current;
    this.head = node;
    
    this.length++;
  }
   
   //Pop the item from the stack
   pop = () => {
    let current = this.head;
    
    //If there is item then remove it 
    //and make the next element as the first
    if(current){
      let elm = current.element;
      current = current.next;
      this.head = current;
      this.length--;
      return elm;
    }
    
    return null;   
  }
  
  //Return the first element in the stack
  peek = () => {   
    if(this.head){    
      return this.head.element;
    }

    return null; 
  }
  
  //Convert the stack to an array
  toArray = () => {
    let arr = [];
    let current = this.head;
    while(current){
      arr.push(current.element);
      current = current.next;
    }
    
    return arr;
  }
  
  //Check if stack is empty
  isEmpty = () => {
    return this.length === 0;
  }
  
  //Return the size of the stack
  size = () => {
    return this.length;
  }
  
  //Clear the stack
  clear = () => {
    this.head = null;
    this.length = 0;
  }
}

 Input: 
 let stack = new stackUsingLL();   //creating new instance of Stack
 stack.push(1);
 stack.push(2);
 stack.push(3);
 console.log(stack.peek());
 console.log(stack.isEmpty());
 console.log(stack.size());
 console.log(stack.pop());
 console.log(stack.toArray());
 console.log(stack.size());
 stack.clear(); //Clear the stack
 console.log(stack.isEmpty());

 Output:
 3
 false
 3
 3
 [2, 1]
 2
 true

We can also wrap this inside a closure to make the implementation private.

let stackUsingLL = (function(){
  //Node
  class Node {
    constructor(elm){
      this.element = elm;
      this.next = null;
    }
  }

 return class stack {
    constructor(){
      this.length = 0;
      this.head = null;
    }

     //Push data in the stack
     push = (elm) => {
      //Create a new node
      let node = new Node(elm),
      current;

      //Add the new node at the top
      current = this.head;
      node.next = current;
      this.head = node;

      this.length++;
    }

     //Pop the item from the stack
     pop = () => {
      let current = this.head;

      //If there is item then remove it 
      //and make the next element as the first
      if(current){
        let elm = current.element;
        current = current.next;
        this.head = current;
        this.length--;
        return elm;
      }

      return null;   
    }

    //Return the first element in the stack
    peek = () => {    
      if(this.head){    
        return this.head.element;
      }

      return null;
    }

    //Convert the stack to an array
    toArray = () => {
      let arr = [];
      let current = this.head;
      while(current){
        arr.push(current.element);
        current = current.next;
      }

      return arr;
    }

    //Check if stack is empty
    isEmpty = () => {
      return this.length === 0;
    }

    //Return the size of the stack
    size = () => {
      return this.length;
    }

    //Clear the stack
    clear = () => {
      this.head = null;
      this.length = 0;
    }
  }
}());

Introducing frontend system design course 🔥 where you will learn to design frontend of 30+ applications.