Implement Queue Using a Linked List Tutorial

Implementing a Queue with a Linked List

A queue can be implemented using a linked list by maintaining references to the front and rear nodes. The queue follows the FIFO (First In, First Out) principle, so new elements are added at the rear and elements are removed from the front.

Unlike an array-based queue, a linked-list implementation does not require elements to be shifted when the front element is removed. By keeping both front and rear references, enqueue and dequeue operations can be performed efficiently.

Front                                  Rear
  ↓                                      ↓
[10 | •] → [20 | •] → [30 | null]
  ↑                                      ↑
Remove                                   Add

Why Use a Linked List for a Queue?

A linked list is useful for queue implementation because inserting a node at the rear and removing a node from the front can both be performed without moving the remaining elements.

The implementation keeps track of two references:

Front: Points to the node that will be removed next.
Rear: Points to the most recently added node.

When the queue is empty, both references are null.

Empty queue:

front = null
rear  = null

The Node Structure

Each element in the linked-list queue is represented by a node. A node contains the value and a reference to the next node in the sequence.

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

The next property connects one node to the next node in the queue. The last node always points to null.

Structure of a Linked-List Queue

Suppose the queue contains 10, 20, and 30. The linked-list representation looks like this:

front
  ↓
[10 | •] → [20 | •] → [30 | null]
                              ↑
                             rear

The front node contains the first element to be processed, while the rear node represents the location where the next element will be attached.

Queue Class

A queue class can maintain the front node, rear node, and optionally the number of elements. Keeping a count makes the size operation constant time.

class Queue {
  constructor() {
    this.front = null;
    this.rear = null;
    this.count = 0;
  }
}

Enqueue in a Linked-List Queue

The enqueue operation adds a new node to the rear of the queue. There are two situations to handle: adding to an empty queue and adding to a non-empty queue.

Adding to an Empty Queue

When the queue is empty, there is no existing rear node. The newly created node therefore becomes both the front and rear.

Before:

front = null
rear  = null

enqueue(10)

After:

front → [10 | null] ← rear

Adding to a Non-Empty Queue

When the queue already contains elements, the new node is connected to the current rear node. The rear reference is then moved to the new node.

Before:

front → [10 | •] → [20 | null] ← rear

enqueue(30)

After:

front → [10 | •] → [20 | •] → [30 | null]
                                      ↑
                                     rear

Enqueue Implementation

enqueue(value) {
  const node = new Node(value);

  if (this.rear === null) {
    this.front = node;
    this.rear = node;
  } else {
    this.rear.next = node;
    this.rear = node;
  }

  this.count++;
}

Because the rear node is already known, no traversal is required to find the insertion point. Therefore, enqueue can be performed in O(1) time.

Dequeue in a Linked-List Queue

The dequeue operation removes the node at the front of the queue. Since the front node is directly available through the front reference, the operation does not require traversal.

Before:

front → [10 | •] → [20 | •] → [30 | null]
                                      ↑
                                     rear

dequeue()

After:

front → [20 | •] → [30 | null]
                            ↑
                           rear

Removed: 10

The front reference is simply moved to the next node.

dequeue() {
  if (this.front === null) {
    return null;
  }

  const value = this.front.value;
  this.front = this.front.next;
  this.count--;

  return value;
}

Handling the Last Element

A special case occurs when the queue contains only one node. After removing that node, both front and rear must become null.

Before:

front → [10 | null] ← rear

dequeue()

After:

front = null
rear  = null

If the rear reference is not updated when the final element is removed, it may continue pointing to a node that is no longer part of the queue. This can cause incorrect behavior during a later enqueue.

Complete Dequeue Implementation

A robust dequeue operation handles both the normal case and the case where the removed node was the final node in the queue.

dequeue() {
  if (this.front === null) {
    return null;
  }

  const value = this.front.value;
  this.front = this.front.next;
  this.count--;

  if (this.front === null) {
    this.rear = null;
  }

  return value;
}

Peek Operation

The peek operation returns the value at the front without removing the node. It can directly access the front reference.

peek() {
  return this.front === null
    ? null
    : this.front.value;
}

Since the front node is directly available, peek takes O(1) time.

Checking Whether the Queue Is Empty

A linked-list queue is empty when its front reference is null. Because a queue maintains both front and rear references, a consistent implementation should have both references set to null when the queue contains no elements.

isEmpty() {
  return this.front === null;
}

Getting the Queue Size

If the implementation maintains a count property, the number of elements can be returned directly.

size() {
  return this.count;
}

Without a stored count, calculating the size would require traversing the linked list, which takes O(n) time. Maintaining a count makes the operation O(1).

Inspecting the Rear Element

Because the queue maintains a rear reference, the last element can also be inspected directly. This is useful when the implementation provides a rear or back operation.

rearValue() {
  return this.rear === null
    ? null
    : this.rear.value;
}

Complete Linked-List Queue

Combining the node structure with front and rear references produces a complete linked-list queue implementation.

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.front = null;
    this.rear = null;
    this.count = 0;
  }

  enqueue(value) {
    const node = new Node(value);

    if (this.rear === null) {
      this.front = node;
      this.rear = node;
    } else {
      this.rear.next = node;
      this.rear = node;
    }

    this.count++;
  }

  dequeue() {
    if (this.front === null) {
      return null;
    }

    const value = this.front.value;
    this.front = this.front.next;
    this.count--;

    if (this.front === null) {
      this.rear = null;
    }

    return value;
  }

  peek() {
    return this.front === null
      ? null
      : this.front.value;
  }

  isEmpty() {
    return this.front === null;
  }

  size() {
    return this.count;
  }

  rearValue() {
    return this.rear === null
      ? null
      : this.rear.value;
  }
}

const queue = new Queue();

queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);

console.log(queue.peek());      // 10
console.log(queue.rearValue()); // 30
console.log(queue.dequeue());   // 10
console.log(queue.dequeue());   // 20
console.log(queue.size());      // 1
console.log(queue.peek());      // 30

Step-by-Step Example

Consider adding three values to an empty linked-list queue.

Step 1: Enqueue 10

front
  ↓
[10 | null]
  ↑
rear

Step 2: Enqueue 20

front
  ↓
[10 | •] → [20 | null]
                   ↑
                  rear

Step 3: Enqueue 30

front
  ↓
[10 | •] → [20 | •] → [30 | null]
                              ↑
                             rear

Step 4: Dequeue

Removed: 10

front
  ↓
[20 | •] → [30 | null]
                   ↑
                  rear

The first node is removed simply by moving the front reference from the old node to its next node. No other nodes need to be moved.

Linked List vs Array Queue

Both arrays and linked lists can implement queues efficiently when the implementation is designed correctly. The main differences are in storage behavior, memory management, and how the queue reuses space.

Feature	Array Queue	Linked-List Queue
Enqueue	O(1) amortized with append	O(1) with rear reference
Dequeue	O(1) with front index	O(1)
Memory layout	Array storage	Separate linked nodes
Capacity	May require resizing or fixed capacity	Grows node by node
Memory overhead	Generally lower per element	Extra reference per node
Storage reuse	Requires indexing, compaction, or circular design	Removed nodes no longer belong to the queue

Complexity Analysis

With both front and rear references, the main queue operations can be performed without traversing the linked list.

Operation	Time Complexity	Reason
Enqueue	O(1)	Rear node is directly available
Dequeue	O(1)	Front node is directly available
Peek	O(1)	Reads the front node
IsEmpty	O(1)	Checks the front reference
Size	O(1)*	Uses a maintained count
Search	O(n)	Requires traversal

*Size is O(1) when the implementation maintains a count. Traversing the linked list to calculate the size would take O(n).

Memory Considerations

A linked-list queue grows dynamically as nodes are created. It does not require a contiguous block of storage for all queue elements, but every node needs additional memory for its next reference.

This means the choice between an array and linked list is not only about operation complexity. Memory overhead, allocation behavior, expected queue size, and the surrounding application can also influence the implementation choice.

Common Mistakes

Traversing the entire linked list during every enqueue instead of maintaining a rear reference.
Forgetting to update the rear when the last node is dequeued.
Not handling dequeue on an empty queue.
Updating the rear but forgetting to connect the old rear to the new node.
Calculating size by traversal when a maintained count would be more efficient.
Confusing the front node with the rear node.

Practical Example: Processing Jobs

A linked-list queue can represent jobs waiting for a worker. Each new job is attached to the rear, while the worker removes jobs from the front.

const queue = new Queue();

queue.enqueue("Send email");
queue.enqueue("Generate invoice");
queue.enqueue("Create backup");

while (!queue.isEmpty()) {
  console.log("Processing:", queue.dequeue());
}

// Processing: Send email
// Processing: Generate invoice
// Processing: Create backup

This pattern is useful whenever work arrives continuously but should be processed in the order in which it was received.

When to Use a Linked-List Queue

A linked-list implementation can be useful when the queue needs dynamic growth and efficient insertion and removal without maintaining a large contiguous array.

The queue size can change significantly during execution.
Constant-time enqueue and dequeue are required.
There is no need for direct indexed access to queue elements.
The application can tolerate the memory overhead of node references.
The implementation benefits from explicit front and rear node management.

Key Takeaways

A linked-list queue uses nodes connected through next references.
The front reference identifies the next node to be removed.
The rear reference identifies where the next node should be added.
Enqueue adds a node at the rear in O(1) time when a rear reference is maintained.
Dequeue removes a node from the front in O(1) time.
When the last node is removed, both front and rear should become null.
A maintained count allows the size operation to run in O(1) time.
Linked-list queues grow dynamically but require additional memory for node references.

Topics

Implement Queue Using a Linked List