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,
data
to store the value of the element andnext
to 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.