Queue Implementation Using Linked List in DSA Javascript - Execution Trace

Concept Flow - Queue Implementation Using Linked List

Create new node

↓

Is queue empty?

Yes→Set head and tail to new node

|No↓

Set tail.next to new node

↓

Update tail to new node

↓

Done

↓

Is queue empty?

Yes→Return underflow

|No↓

Save head node data

↓

Move head to head.next

↓

If head is null, set tail to null

↓

Return saved data

↓

Done

This flow shows how nodes are added at the tail and removed from the head in a linked list queue.

Execution Sample

DSA Javascript

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;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
  }

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

const q = new Queue();
q.enqueue(10);
q.enqueue(20);
q.dequeue();
q.enqueue(30);

This code creates a queue using a linked list, adds 10 and 20, removes one element, then adds 30.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	enqueue(10)	10	head -> 10, tail -> 10	10 -> null
2	enqueue(20)	10 -> 20	tail.next -> 20, tail -> 20	10 -> 20 -> null
3	dequeue()	20	head -> 20	20 -> null
4	enqueue(30)	20 -> 30	tail.next -> 30, tail -> 30	20 -> 30 -> null
5	End	20 -> 30	No change	20 -> 30 -> null

💡 No more operations; queue has two nodes with values 20 and 30.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
head	null	Node(10)	Node(10)	Node(20)	Node(20)	Node(20)
tail	null	Node(10)	Node(20)	Node(20)	Node(30)	Node(30)
list size	0	1	2	1	2	2

Key Moments - 3 Insights

Why do we update tail.next when enqueueing if tail is not null?

Because tail points to the last node, we link the new node after tail by setting tail.next to newNode, then update tail to newNode. See step 2 and 4 in execution_table.

What happens to tail when we dequeue the last element?

When head becomes null after dequeue, tail is also set to null to indicate the queue is empty. This is shown in step 3 where after removing 10, head points to 20 and tail remains 20.

Why does dequeue return null if head is null?

Because an empty queue has no nodes, so no value to return. This prevents errors. This is the check at the start of dequeue method.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the value of head after dequeue?

A Node with value 10

B Node with value 20

C null

D Node with value 30

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 3 in execution_table.

At which step does the queue become empty?

A After step 1

B After step 3

C Never in this trace

D After step 4

💡 Hint

Look at the 'Nodes in List' column in execution_table; queue always has nodes.

If we enqueue(40) after step 4, what will tail point to?

A Node with value 40

B Node with value 30

C Node with value 20

D null

💡 Hint

Enqueue adds new node at tail; tail updates to new node. See steps 2 and 4.

Concept Snapshot

Queue using linked list:
- Enqueue adds node at tail
- Dequeue removes node from head
- If empty, head and tail are null
- tail.next links new node
- Dequeue updates head and tail if empty
- FIFO order maintained

Full Transcript

This visual trace shows how a queue is implemented using a linked list in JavaScript. We create nodes with values and link them. Enqueue adds nodes at the tail end, updating tail pointer. Dequeue removes nodes from the head, updating head pointer. If the queue becomes empty, both head and tail are set to null. The execution table tracks each operation step-by-step, showing the nodes in the list, pointer changes, and the visual linked list state. Variable tracker shows how head, tail, and list size change after each operation. Key moments clarify why tail.next is updated during enqueue, what happens to tail when dequeue empties the queue, and why dequeue returns null if empty. The quiz tests understanding of pointer changes and queue state during operations. This helps beginners see exactly how the linked list queue changes with each enqueue and dequeue.

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