Implement queue using linked list

Posted on | by Prashant Yadav

Posted in , ,

Learn how to implement queue using linked list in javascript.

A queue is an ordered collection of data in which data is stored in FIFO (First In First Out) order. We will see how to implement it using single linked list in javascript.

List of operations performed on queue

  • enqueue: Adds new data at the end of the queue.
  • dequeue: Removes data from the front of the queue and returns it.
  • front: Returns the first data from the front of the queue.
  • rear: Returns the first data from the end of the queue.
  • toArray: Returns the queue as the array.
  • size: Returns the length of the queue.
  • isEmpty: Returns true if queue is empty, false otherwise.
  • clear: Clears the queue.

Implementing queue using linked list

We will implement queue using linked list with two different approaches in javascript.
1) Using function as a constructor.
2) Using class.

We will use two extra variables length to keep track of the size of the queue and head to keep track of the list.

//Queue using linkedlist
function queueUsingLL(){
  //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
}

Adding an item in the queue

To add an item in the queue, we will check if the list is empty then use the new node as the first element else add the new node to the end of the existing nodes.

Enqueue in (queue using linked list)

  //Enqueue data in the queue
  this.enqueue = function(elm){
    let node = new Node(elm),
    current;
  
    //If head is empty then 
    //Add the node at the beginning
    if(head === null){
      head = node;
    }else{
      //Else add the node as the
      //Next element of the existing list
      current = head;
      while(current.next){
        current = current.next;
      }

      current.next = node;
    }

    //Increase the length
    length++;
  }

Remove an item from the queue

To remove an item from the queue, we just have to remove the first node from the list by making head to point to the very next node and return the removed node.

Dequeue in (queue using linked list)

  //Remove the item from the queue
  this.dequeue = 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 first item in the queue

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

    return null;
  }

Peek the last item in the queue

//Return the last element in the queue
  this.rear = function(){    
    let current = head;
    
    //If head is empty
    //Return null
    if(current === null){
      return null;
    }
    
    //Return the last elememnt
    while(current.next){
      current = current.next;
    }

    return current.element;
  }

Convert the queue to an array

  //Convert the queue 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 queue

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

Check if queue is empty

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

Clear the queue

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

Complete code for the queue using linked list

//Queue using linkedlist
function queueUsingLL(){
  //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;
  
  //Enqueue data in the queue
  this.enqueue = function(elm){
    let node = new Node(elm),
    current;
  
    //If head is empty then 
    //Add the node at the beginning
    if(head === null){
      head = node;
    }else{
      //Else add the node as the
      //Next element of the existing list
      current = head;
      while(current.next){
        current = current.next;
      }

      current.next = node;
    }

    //Increase the length
    length++;
  }
  
  //Remove the item from the queue
  this.dequeue = 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 queue
  this.front = function(){    
    if(head){    
      return head.element;
    }

    return null;
  }
  
  //Return the last element in the queue
  this.rear = function(){    
    let current = head;
    
    //If head is empty
    //Return null
    if(current === null){
      return null;
    }
    
    //Return the last elememnt
    while(current.next){
      current = current.next;
    }

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

Input:
let queue = new queueUsingLL();
console.log(queue.isEmpty());
queue.enqueue('pranav');
queue.enqueue('sachin');
queue.enqueue('yogesh');
console.log(queue.toArray());
queue.dequeue();
queue.dequeue();
console.log(queue.toArray());
queue.enqueue('prashant');
queue.enqueue('yadav');
queue.dequeue();
console.log(queue.toArray());
console.log(queue.size());
console.log(queue.front());
console.log(queue.rear());

Output:
true
["pranav", "sachin", "yogesh"]
["yogesh"]
["prashant", "yadav"]
2
"prashant"
"yadav"

We can use the closure and IIFE (Immediately Invoked Function Expression) to make the properties and methods of the
above implementation private.

let Queue = (function(){
  //Queue using linkedlist
  return function queueUsingLL(){
    //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;

    //Enqueue data in the queue
    this.enqueue = function(elm){
      let node = new Node(elm),
      current;

      //If head is empty then 
      //Add the node at the beginning
      if(head === null){
        head = node;
      }else{
        //Else add the node as the
        //Next element of the existing list
        current = head;
        while(current.next){
          current = current.next;
        }

        current.next = node;
      }

      //Increase the length
      length++;
    }

    //Remove the item from the queue
    this.dequeue = 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 queue
    this.front = function(){    
      if(head){    
        return head.element;
      }

      return null;
    }

    //Return the last element in the queue
    this.rear = function(){    
      let current = head;

      //If head is empty
      //Return null
      if(current === null){
        return null;
      }

      //Return the last elememnt
      while(current.next){
        current = current.next;
      }

      return current.element;
    }

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

      return arr;
    }

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

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

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

  }
}());

Class based implementation of queue using single linked list in javascript.

We will use two different classes to make this implementation.
1) To create the nodes of the list

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

2) To implement the queue

class QueueUsingLL {
  constructor(){
    this.length = 0;
    this.head = null;
  }
  
   //Push data in the queue
   enqueue = (elm) => {
    let node = new Node(elm),
    current;
  
    //If head is empty then 
    //Add the node at the beginning
    if(this.head === null){
      this.head = node;
    }else{
      //Else add the node as the
      //Next element of the existing list
      current = this.head;
      while(current.next){
        current = current.next;
      }

      current.next = node;
    }

    //Increase the length
    this.length++;
  }
   
   //Remove the item from the queue
   dequeue = () => {
    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 queue
  front = () => {    
    if(this.head){    
      return this.head.element;
    }

    return null;
  }
  
  //Return the last element in the queue
  rear = () => {    
    let current = this.head;
    
    //If head is empty
    //Return null
    if(current === null){
      return null;
    }
    
    //Return the last elememnt
    while(current.next){
      current = current.next;
    }

    return current.element;
  }
  
  //Convert the queue 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;
  }
}

We can also wrap this in closure and IIFE to make its method and properties private.

let Queue = (function(){
  //Node
  class Node {
    constructor(elm){
      this.element = elm;
      this.next = null;
    }
  }
  
  //Queue
  return class QueueUsingLL {
    constructor(){
      this.length = 0;
      this.head = null;
    }

     //Push data in the queue
     enqueue = (elm) => {
      let node = new Node(elm),
      current;

      //If head is empty then 
      //Add the node at the beginning
      if(this.head === null){
        this.head = node;
      }else{
        //Else add the node as the
        //Next element of the existing list
        current = this.head;
        while(current.next){
          current = current.next;
        }

        current.next = node;
      }

      //Increase the length
      this.length++;
    }

     //Remove the item from the queue
     dequeue = () => {
      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 queue
    front = () => {    
      if(this.head){    
        return this.head.element;
      }

      return null;
    }

    //Return the last element in the queue
    rear = () => {    
      let current = this.head;

      //If head is empty
      //Return null
      if(current === null){
        return null;
      }

      //Return the last elememnt
      while(current.next){
        current = current.next;
      }

      return current.element;
    }

    //Convert the queue 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.