JavaScript Program for Implementation of Queue using Linked List
A queue is a linear data structure that follows the First In, First Out, FIFO principle, where elements are added at the rear and removed from the front. We must implement a queue data structure using a linked list and provide operations such as enqueue, dequeue, peek, and isEmpty. Linked list-based queues offer constant-time enqueue, dequeue, peek, and isEmpty operations, making them efficient for many applications.
Approach
- To implement a queue using a linked list, we’ll define a Node class to represent individual elements and a Queue class to manage the operations on the queue.
- The Node class represents an individual element in the queue. It contains two properties,
datato store the value of the element andnextto point to the next node in the queue. - The Queue class manages the operations on the queue. It contains methods for enqueue, dequeue, peek, and isEmpty operations.
Example: The code below shows a JavaScript program for implementing a queue using a linked list.
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class Queue {
constructor() {
this.front = null;
this.rear = null;
this.size = 0;
}
enqueue(data) {
const newNode = new Node(data);
if (!this.front) {
this.front = newNode;
} else {
this.rear.next = newNode;
}
this.rear = newNode;
this.size++;
}
dequeue() {
if (!this.front) return null;
const removed = this.front;
this.front = this.front.next;
if (!this.front) this.rear = null;
this.size--;
return removed.data;
}
peek() {
return this.front ? this.front.data : null;
}
isEmpty() {
return this.size === 0;
}
}
const queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
console.log(queue.dequeue());
console.log(queue.peek());
console.log(queue.isEmpty());
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.isEmpty());
Output
10 20 false 20 30 true
Time Complexity: O(1).
Space Complexity: O(n), depends on the number of elements in the queue.
Contact Us