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 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.
//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; } } }());