Queue Implementation Using Linked List in DSA Javascript

Mental Model

A queue is a line where the first person in is the first person out. Using a linked list means each person holds a pointer to the next one in line.

Analogy: Imagine a line of people waiting to buy tickets. The first person to get in line is the first to get the ticket and leave. Each person knows who is behind them, but not the whole line.

front -> [1] -> [2] -> [3] -> null
rear ↑

Dry Run Walkthrough

Input: Start with empty queue, enqueue 1, enqueue 2, dequeue, enqueue 3

Goal: Show how the queue changes step-by-step using linked list pointers

Step 1: enqueue 1 into empty queue

front -> [1] -> null
rear ↑

Why: First element becomes both front and rear

Step 2: enqueue 2 at rear

front -> [1] -> [2] -> null
rear ↑

Why: Add new node after rear and update rear pointer

Step 3: dequeue front element (1)

front -> [2] -> null
rear ↑

Why: Remove front node and move front pointer to next

Step 4: enqueue 3 at rear

front -> [2] -> [3] -> null
rear ↑

Why: Add new node after rear and update rear pointer

Result:

front -> [2] -> [3] -> null
rear ↑

Annotated Code

DSA Javascript

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

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

  enqueue(value) {
    const newNode = new Node(value);
    if (this.rear === null) {
      this.front = newNode;
      this.rear = newNode;
      return;
    }
    this.rear.next = newNode; // link new node after rear
    this.rear = newNode; // update rear to new node
  }

  dequeue() {
    if (this.front === null) {
      return null; // queue empty
    }
    const dequeuedValue = this.front.value;
    this.front = this.front.next; // move front to next node
    if (this.front === null) {
      this.rear = null; // queue became empty
    }
    return dequeuedValue;
  }

  printQueue() {
    let curr = this.front;
    let result = '';
    while (curr !== null) {
      result += curr.value + ' -> ';
      curr = curr.next;
    }
    result += 'null';
    console.log(result);
  }
}

// Driver code
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.dequeue();
queue.enqueue(3);
queue.printQueue();

this.rear.next = newNode; // link new node after rear

link new node after current rear to keep queue order

this.rear = newNode; // update rear to new node

move rear pointer to new last node

this.front = this.front.next; // move front to next node

remove front node by moving front pointer forward

if (this.front === null) { this.rear = null; // queue became empty }

if queue is empty after dequeue, reset rear pointer

Output

2 -> 3 -> null

Complexity Analysis

Time: O(1) for both enqueue and dequeue because we only update pointers without traversing the list

Space: O(n) because each element is stored as a node in the linked list

vs Alternative: Compared to array-based queue, linked list avoids costly shifting on dequeue, making operations faster

Edge Cases

dequeue from empty queue

returns null without error

DSA Javascript

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

enqueue into empty queue

front and rear both point to the new node

DSA Javascript

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

dequeue last element

front and rear both become null

DSA Javascript

if (this.front === null) {
      this.rear = null; // queue became empty
    }

When to Use This Pattern

When you need a first-in-first-out order and want efficient add/remove without shifting, use a linked list queue to keep operations fast.

Common Mistakes

Mistake: Not updating rear pointer after enqueue, causing rear to point to old node
Fix: Always update rear to the new node after linking it

Mistake: Not resetting rear to null when queue becomes empty after dequeue
Fix: Check if front is null after dequeue and set rear to null

Mistake: Trying to traverse from rear to front which is not possible in singly linked list
Fix: Only traverse from front to rear using next pointers

Summary

Implements a queue using a linked list where elements are added at rear and removed from front.

Use when you want a queue with efficient enqueue and dequeue operations without shifting elements.

The key is to keep track of both front and rear pointers to add and remove nodes in constant time.

Practice

1. What is the main advantage of implementing a Queue using a linked list instead of an array?

easy

A. Simpler syntax for insertion and deletion

B. Faster random access to elements

C. Uses less memory than arrays

D. Dynamic size without fixed capacity limits

Solution

1. Step 1: Understand queue size limitations in arrays

   Arrays have fixed size or require resizing, which can be costly.

2. Step 2: Linked list dynamic size advantage

   Linked lists grow and shrink dynamically without fixed capacity limits.

3. Final Answer:

   Dynamic size without fixed capacity limits -> Option D

4. Quick Check:

   Linked list queues grow dynamically [OK]

Hint: Linked lists grow dynamically, arrays have fixed size [OK]

Common Mistakes:

• Thinking linked lists allow faster random access
• Assuming linked lists always use less memory
• Confusing syntax simplicity with performance

2. Which of the following is the correct way to add a new node to the end of a linked list queue in JavaScript?

easy

A. tail.next = newNode; tail = newNode;

B. head.next = newNode; head = newNode;

C. newNode.next = tail; tail = newNode;

D. newNode.next = head; head = newNode;

Solution

1. Step 1: Identify tail pointer usage in queue enqueue

   New nodes are added at the tail; tail.next points to new node.

2. Step 2: Update tail to new node

   After adding, tail must point to the new node to keep queue end updated.

3. Final Answer:

   tail.next = newNode; tail = newNode; -> Option A

4. Quick Check:

   Enqueue adds at tail [OK]

Hint: Enqueue adds at tail: tail.next = newNode; tail = newNode [OK]

Common Mistakes:

• Adding new node at head instead of tail
• Not updating tail pointer after insertion
• Confusing head and tail pointers

3. You want to implement a method peek() for a linked list queue that returns the front element without removing it. Which is the correct implementation?

easy

A. return this.head ? this.head.value : null;

B. return this.tail ? this.tail.value : null;

C. return this.head.next ? this.head.next.value : null;

D. return this.tail.next ? this.tail.next.value : null;

Solution

1. Step 1: Understand peek operation in queue

   Peek returns front element without removing it, which is at head in linked list queue.

2. Step 2: Check correct pointer for front element

   Head points to front node; tail points to end node. So return head.value if head exists.

3. Final Answer:

   return this.head ? this.head.value : null; -> Option A

4. Quick Check:

   Peek returns head value [OK]

Hint: Peek returns head value without dequeue [OK]

Common Mistakes:

• Returning tail value instead of head
• Accessing next of tail which is always null
• Returning head.next value which skips front

4. Consider this JavaScript code for a linked list queue:

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

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
  }
  enqueue(value) {
    const newNode = new Node(value);
    if (!this.tail) {
      this.head = newNode;
      this.tail = newNode;
      return;
    }
    this.tail.next = newNode;
    this.tail = newNode;
  }
  dequeue() {
    if (!this.head) return null;
    const val = this.head.value;
    this.head = this.head.next;
    if (!this.head) this.tail = null;
    return val;
  }
}

const q = new Queue();
q.enqueue(10);
q.enqueue(20);
q.dequeue();
q.enqueue(30);
q.dequeue();
q.enqueue(40);
q.enqueue(50);
q.dequeue();
console.log(q.head.value);

What will be printed?

medium

A. 20

B. 40

C. 50

D. 30

Solution

1. Step 1: Trace enqueue and dequeue operations

   Queue after operations: - enqueue 10: head=10, tail=10 - enqueue 20: head=10->20, tail=20 - dequeue: removes 10, head=20 - enqueue 30: head=20->30, tail=30 - dequeue: removes 20, head=30 - enqueue 40: head=30->40, tail=40 - enqueue 50: head=30->40->50, tail=50 - dequeue: removes 30, head=40

2. Step 2: Identify current head value

   After last dequeue, head points to node with value 40.

3. Final Answer:

   40 -> Option B

4. Quick Check:

   Final head value after operations = 40 [OK]

Hint: Track head after each dequeue to find current front [OK]

Common Mistakes:

• Forgetting to update tail when queue becomes empty
• Mixing up enqueue and dequeue order
• Assuming head value is unchanged after dequeue

5. The following dequeue method for a linked list queue has a bug:

dequeue() {
  if (!this.head) return null;
  const val = this.head.value;
  this.head = this.head.next;
  return val;
}

What is the problem?

medium

A. It removes the tail instead of the head

B. It returns the wrong value

C. It does not update tail when queue becomes empty

D. It causes infinite loop

Solution

1. Step 1: Analyze dequeue method behavior

   It removes head by moving head pointer to next node and returns old head value.

2. Step 2: Identify missing tail update

   If after removal head becomes null (queue empty), tail still points to old node causing inconsistency.

3. Final Answer:

   It does not update tail when queue becomes empty -> Option C

4. Quick Check:

   Empty queue must reset tail = null [OK]

Hint: Reset tail to null when head becomes null after dequeue [OK]

Common Mistakes:

• Ignoring tail pointer update on empty queue
• Confusing head and tail roles
• Assuming dequeue removes tail node