Queue

Using Linked List

Queue Implementation Using Linked List

Building a queue on top of a linked list sidesteps the fixed-capacity problem that array-backed queues have — nodes get allocated on demand, so the queue can keep growing as long as there's memory available.

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

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

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

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
Advertisement

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
Daily DSA Challenge by Scale Engineer

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

Done With the Learning

Mark Queue implementation using Linked List as done and view it on your dashboard

Explore other implementation

Using Array