Queue Data Structure

Part 2: Implementing Queue Using Singly Linked List

A queue is a data structure that follows the First-In/First-Out principle(popularly known as FIFO), meaning the first element that’s added will be the first to be removed.

Queue at the supermarket

Creating A New Node

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

Creating a Queue Class

class Queue {
  constructor(value){
    const newNode = new Node(value)
    this.first = newNode
    this.last = newNode
    this.length = 1
  }
}

//creating new instance of Queue class
let q1 = new Queue(10)

Adding Node To End of List

//PROCESS:
    //create new Node using Node class
  
    //if list is empty:
      //set the first and last to equal to new Node
    //else
      //add Node to the end of list

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

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

Removing The First Node From The List

 //PROCESS:
  
    //if list is empty:
      // return undefined
  
    //create pointer variable and set it to first Node in list
  
    //if list has 1 Node:
      // set the first and last to point to null
    //else
      //set the second node in list as the head
      //remove the first node in the list

    //reduce length by 1
    //return the Node that was deleted
  

  dequeue(){
    if(this.length === 0) return undefined
    
    const temp = this.first

    if(this.length === 1){
      this.first = null
      this.last = null
    } else {   
      this.first = this.first.next
      temp.next = null
    }

    this.length--
    return temp
  }

How It Looks All Together

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

class Queue {
  constructor(value){
    const newNode = new Node(value)
    this.first = newNode
    this.last = newNode
    this.length = 1
  }

  
  //ADDING NODE TO END OF LIST
  enqueue(value){
    const newNode = new Node(value)

    if(this.length === 0){
      this.first = newNode
      this.last = newNode
    } else {
      this.last.next = newNode
      this.last = newNode
    }
    this.length++
    return this
  }
  
  //REMOVING NODE FROM BEGINNING OF LIST
  dequeue(){
    if(this.length === 0) return undefined
    
    const temp = this.first

    if(this.length === 1){
      this.first = null
      this.last = null
    } else {   
      this.first = this.first.next
      temp.next = null
    }

    this.length--
    return temp
  }
}

//creating new instance of Queue class
let q1 = new Queue(10)

//adding node at the end of list
q1.enqueue(20)

//removing node at the beginning of list
q1.dequeue()

Check out Part 1: Implementing Queue Using Arrays

Citation

Queue - Linked List Implementation - GeeksforGeeks

Photo by Adrien Delforge on Unsplash