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.

How Does It Work?

Every node sits somewhere in memory at its own address, shown in grey underneath it. Each box has two cells: the value on the left, and on the right the next field — which does not contain the following node, only the address where it lives. The queue itself stores nothing but two addresses of its own, front and rear. The addresses below are made up and kept short for readability; real ones are much longer, but they behave exactly like this:

  1. An empty queue is just two null pointers. There is no array to allocate and no capacity to pick up front.
    front / rearnullfront = null, rear = null, size 0
  2. enqueue(10): memory hands back a node at 0x1A. The queue was empty, so both front and rear now store that address, and the node's next is null.
    front10null0x1Afront = 0x1A, rear = 0x1A, size 1
  3. enqueue(20): the new node lives at 0x2F, so 0x1A's next is changed from null to 0x2F and rear is updated to 0x2F. front still holds 0x1A and never had to be touched.
    frontrear100x2F0x1A20null0x2Fnew nodefront = 0x1A, rear = 0x2F, size 2
  4. enqueue(30): the same two writes again — 0x2F's next becomes 0x3C, and rear becomes 0x3C. Nothing scans the list looking for the end, because rear already holds its address; that is what keeps enqueue O(1).
    frontrear100x2F0x1A200x3C0x2F30null0x3Cnew nodefront = 0x1A, rear = 0x3C, size 3
  5. dequeue(): front is overwritten with the address stored in 0x1A's next, which is 0x2F. The node at 0x1A is now unreachable from the queue and can be freed. No other node moved, and none of the addresses changed.
    frontrear100x1Adetached200x3C0x2F30null0x3Cfront = 0x2F, rear = 0x3C, size 2
Node just allocatedDetached by dequeueIn the queue

Follow one address through the whole sequence and the structure gives itself away: 0x2F is written into 0x1A's next field in step 3, is held by rear in step 3, and becomes the new front in step 5 — all without the node at 0x2F ever moving. A linked list is reordered by rewriting addresses, never by relocating data. That is also why the nodes need not be next to each other in memory at all.

Compare this with the array version. There, the capacity is fixed at creation and dequeued slots strand behind front unless the indices wrap around. Here the queue only ever holds as many nodes as it needs, and a dequeued node is handed straight back to memory. The trade is in the next reference itself: every element costs an extra pointer, and because nodes are allocated separately they can end up scattered in memory rather than sitting contiguously the way array elements do.

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

Both ends are held by a pointer, so neither operation ever walks the list. The cost stays flat however long the queue gets:

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