Queue Implementation Using Linked List

Queue Implementation Using Linked List

Implementing a Queue using a linked list provides dynamic memory allocation and efficient insertion/removal operations. Unlike array implementation, linked list queues don't have fixed capacity limitations and can grow dynamically as needed.

Implementation Steps

  1. Define a Node class with data and next pointer attributes
  2. Create Queue class with front and rear pointers initialized to null
  3. Implement enqueue by adding nodes at the rear
  4. Implement dequeue by removing nodes from the front
  5. Maintain proper pointer connections during operations

Basic Class Structure

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}
class LinkedListQueue {
  constructor() {
    this.front = null;
    this.rear = null;
    this.size = 0;
  }
  isEmpty() {
    return this.front === null;
  }

Note: Each node contains the data and a reference to the next node. The queue maintains references to both ends (front and rear) for efficient operations.

Enqueue Algorithm

  1. Create a new node with the given data
  2. If queue is empty, set both front and rear to the new node
  3. Else, set rear.next to the new node and update rear pointer
  4. Increment the size counter
Before Enqueue:
front → [A|•] → [B|•] → null
After Enqueue(C):
front → [A|•] → [B|•] → [C|•] → null
(rear updated)

Dequeue Algorithm

  1. Check if queue is empty (front === null)
  2. Store the front node to return later
  3. Move front pointer to front.next
  4. If front becomes null (queue is now empty), set rear to null
  5. Decrement the size counter
  6. Return the stored node's data
Before Dequeue:
front → [A|•] → [B|•] → [C|•] → null
After Dequeue():
front → [B|•] → [C|•] → null
(returns A)

Operation Visualization

StepQueue State
Initial empty queue:front → null, rear → null
Enqueue(10):front → [10|•] → null, rear → [10|•]
Enqueue(20):front → [10|•] → [20|•] → null, rear → [20|•]
Enqueue(30):front → [10|•] → [20|•] → [30|•] → null, rear → [30|•]
Dequeue():Returns 10, front → [20|•] → [30|•] → null, rear → [30|•]

Time & Space Complexity

  • Enqueue Operation: O(1) - Constant time to add at tail
  • Dequeue Operation: O(1) - Constant time to remove from head
  • Peek Operation: O(1) - Direct access via front pointer
  • Space Usage: O(n) - Linear space for storing elements plus pointer overhead

Pros and Cons

  • Pros: No fixed size limitation - grows dynamically
  • Pros: Efficient O(1) operations for both enqueue and dequeue
  • Pros: No wasted memory (only allocates what's needed)
  • Cons: Extra memory for node pointers (next references)
  • Cons: Not cache-friendly (nodes may be scattered in memory)

When to Use Linked List Queue

Linked list queues are particularly useful when the maximum size isn't known in advance or when frequent insertions/deletions are required.

  • When the maximum queue size is unpredictable
  • When memory efficiency is more important than cache performance
  • In applications with frequent dynamic memory allocation/deallocation

Queue Implementation (Enqueue & Dequeue)

// Queue Implementation in JavaScript (Linked List)
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.front = null;
    this.rear = null;
  }
  
  // Add element to the rear (enqueue)
  enqueue(item) {
    const newNode = new Node(item);
    if (this.rear === null) {
      this.front = this.rear = newNode;
    } else {
      this.rear.next = newNode;
      this.rear = newNode;
    }
  }
  
  // Remove element from front (dequeue)
  dequeue() {
    if (this.front === null) {
      return "Queue Underflow";
    }
    const temp = this.front;
    this.front = temp.next;
    
    if (this.front === null) {
      this.rear = null;
    }
    return temp.data;
  }

  // Check if queue is empty
  isEmpty() {
    return this.front === null;
  }
}

// Usage Example
const queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
console.log(queue.dequeue()); // 10
console.log(queue.dequeue()); // 20
console.log(queue.isEmpty()); // false

Explore other implementation

Using Array