Stack Data Structure

Part 2: Implementing Stack Using Singly Linked List

Stack is a data structure that follows the Last-In/First-Out principle(popularly known as LIFO), meaning the most recently added element is the first to remove.

Image Source: https://unsplash.com/photos/GlTjWBMBGCc

Creating A New Node

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

Creating a Stack Class

//PROCESS: 
  //create new Node using the Node class
  //set the new Node as the top item
  //increase the length by 1
  
class Stack {
  constructor(value){
    const newNode = new Node(value)
    this.top = newNode
    this.length = 1
  }
  
}

//creating new instance of Stack class
let stack1 = new Stack(10)

Adding Items To The List

It is more efficient to add and remove items at the beginning of a linked list because the time complexity for both operations will be O(1). Otherwise, the time complexity becomes O(n) when removing an item at the end of a list. This is because this operation requires one to traverse the list first in order to remove the last Node.

//PROCESS:
    //create new Node using the Node class

    //if stack is empty:
      //set the new Node as the top
    //else
      //set the new Node to point to the first Node in list
      //set the new Node as the first Node in list

    //increase length by 1
    //return enire list
    
  addNode(value){
    const newNode = new Node(value)

    if(this.length === 0){
      this.top = newNode
    } else {    
      newNode.next = this.top
      this.top = newNode
    }
    this.length++
    return this  
  }

Removing Node From The List

  //PROCESS:
    //create a variable that points to the first Node in list

    //if stack is empty:  
      //return undefined
  
    //else
      //remove return Node from list 
      //reduce length of list by 1
     // return the Node that was deleted

  
  removeNode(){
    let temp = this.top;
    
    if(this.length === 0){
      return undefined
    }
    //removes node from list
    this.top = this.top.next
    temp.next = null
    
    this.length--
    return temp
  }

How It Looks All Together;

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

class Stack {
  constructor(value){
    const newNode = new Node(value)
    this.top = newNode
    this.length = 1
  }

    //ADDING NEW NODE TO LIST
  addNode(value){
    const newNode = new Node(value)

    if(this.length === 0){
      this.top = newNode
    } else {    
      newNode.next = this.top
      this.top = newNode
    }
    this.length++
    return this  
  }

  //REMOVING NODE FROM LIST
  removeNode(){
    let temp = this.top;
    
    if(this.length === 0){
      return undefined
    }
    //removes node from list
    this.top = this.top.next
    temp.next = null
    
    this.length--
    return temp
  }
}

//creating new instance of Stack class
let stack1 = new Stack(10)

//adding new node to the 'stack1' instance
stack1.addNode(20)

Check out Part 1: How To Implement A Stack Using Arrays

Citation

Implement a stack using singly linked list - GeeksforGeeks

Photo by Annie Spratt on Unsplash