Queue Implementation Using Linked List in DSA Typescript - 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

↓

Dequeue operation

↓

Is queue empty?

Yes→Return null or error

| No↓

Save head node data

↓

Update head to head.next

↓

If head is null, set tail to null

↓

Return saved data

↓

Done

This flow shows how nodes are added to the tail and removed from the head of the linked list to implement queue operations.

Execution Sample

DSA Typescript

enqueue(10)
enqueue(20)
dequeue()
enqueue(30)
dequeue()

This code adds 10 and 20 to the queue, removes one element, adds 30, then removes another element.

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	dequeue()	30	head -> 30	30 -> null
6	dequeue()	empty	head -> null, tail -> null	null

💡 Queue is empty after last dequeue, no more elements to remove.

Variable Tracker

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

Key Moments - 3 Insights

Why do we update tail.next when enqueueing but head when dequeueing?

Because enqueue adds at the end (tail), so tail.next points to new node (see Step 2 and 4). Dequeue removes from the front (head), so head moves forward (see Step 3 and 5).

What happens when the last element is dequeued?

Both head and tail become null to show the queue is empty (see Step 6). This prevents dangling pointers.

Why do we check if the queue is empty before enqueueing or dequeueing?

To handle special cases: if empty, enqueue sets both head and tail to new node (Step 1), and dequeue returns null or error if no nodes (Step 6).

Visual Quiz - 3 Questions

Look at the execution table, what is the visual state after Step 4?

A 20 -> 30 -> null

B 10 -> 20 -> 30 -> null

C 30 -> null

D 10 -> 20 -> null

💡 Hint

Check the 'Visual State' column for Step 4 in the execution_table.

At which step does the queue become empty?

A Step 3

B Step 5

C Step 6

D Step 2

💡 Hint

Look at the 'Nodes in List' and 'Pointer Changes' columns to see when head and tail become null.

If we enqueue(40) after Step 6, what will be the head and tail?

A head -> null, tail -> Node(40)

B head -> Node(40), tail -> Node(40)

C head -> Node(30), tail -> Node(40)

D head -> Node(40), tail -> null

💡 Hint

After empty queue, enqueue sets both head and tail to new node (see Step 1).

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 points to new node on enqueue
- Head moves forward on dequeue
- Size tracks number of elements

Full Transcript

This visualization shows how a queue is implemented using a linked list. Enqueue adds a new node at the tail end, updating tail.next and tail pointer. Dequeue removes the node at the head, moving the head pointer forward. When the queue is empty, both head and tail are null. The execution table traces 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 size change after each operation. Key moments clarify common confusions about pointer updates and empty queue handling. The quiz tests understanding of queue state at different steps.

Practice

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

easy

A. Dynamic size without fixed capacity

B. Faster random access to elements

C. Uses less memory than arrays

D. Elements are stored in sorted order automatically

Solution

1. Step 1: Understand array limitations

   Arrays have fixed size or require resizing which is costly.

2. Step 2: Linked list flexibility

   Linked lists grow dynamically without fixed capacity limits.

3. Final Answer:

   Dynamic size without fixed capacity -> Option A

4. Quick Check:

   Linked list queues grow dynamically = A [OK]

Hint: Linked list queues grow dynamically, arrays do not [OK]

Common Mistakes:

• Thinking linked lists allow faster random access
• Assuming linked lists use less memory always
• Believing queues sort elements automatically

2. Which of the following is the correct TypeScript syntax to define a node class for a linked list queue?

easy

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

B. class Node { value: number; next: Node | null; constructor(value: number) { this.value = value; this.next = null; } }

C. class Node { val: number; next: Node | null; constructor(val: number) { this.val = val; this.next = null; } }

D. class Node { value: number; next: Node; constructor(value: number) { this.value = value; this.next = undefined; } }

Solution

1. Step 1: Check property types

   Node must have a value and next pointer which can be null.

2. Step 2: Validate constructor initialization

   Constructor sets value and initializes next to null.

3. Final Answer:

   class Node { value: number; next: Node | null; constructor(value: number) { this.value = value; this.next = null; } } -> Option B

4. Quick Check:

   Node next can be null, initialized in constructor = D [OK]

Hint: Node next pointer must allow null for end of list [OK]

Common Mistakes:

• Setting next to undefined instead of null
• Using wrong property names like val instead of value
• Declaring next as only Node without null option

3. Consider this TypeScript code snippet for a linked list queue:

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

class Queue {
  front: Node | null = null;
  rear: Node | null = null;

  enqueue(value: number) {
    const newNode = new Node(value);
    if (!this.rear) {
      this.front = this.rear = newNode;
      return;
    }
    this.rear.next = newNode;
    this.rear = newNode;
  }

  dequeue(): number | null {
    if (!this.front) return null;
    const value = this.front.value;
    this.front = this.front.next;
    if (!this.front) this.rear = null;
    return value;
  }
}

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();

What is the value returned by the last dequeue() call?

medium

A. 50

B. 40

C. 30

D. 20

Solution

1. Step 1: Trace enqueue and dequeue operations

   Queue after operations: - enqueue 10: front=10, rear=10 - enqueue 20: front=10, rear=20 - dequeue(): removes 10, front=20 - enqueue 30: rear=30 - dequeue(): removes 20, front=30 - enqueue 40: rear=40 - enqueue 50: rear=50 - dequeue(): removes 30, front=40

2. Step 2: Identify last dequeue return value

   The last dequeue removes 30 and returns it.

3. Final Answer:

   30 -> Option C

4. Quick Check:

   Last dequeue returns 30 = A [OK]

Hint: Track front pointer after each dequeue [OK]

Common Mistakes:

• Confusing rear value with dequeued value
• Not updating front after dequeue
• Assuming dequeue returns rear value

4. The following TypeScript code attempts to implement dequeue() for a linked list queue:

dequeue(): number | null {
  if (!this.front) return null;
  const value = this.front.value;
  this.front = this.front.next;
  return value;
}

What is the bug in this code?

medium

A. It returns the wrong value from the queue

B. It incorrectly sets front to null always

C. It does not check if front is null before accessing value

D. It does not update rear when queue becomes empty

Solution

1. Step 1: Analyze dequeue logic

   It removes front node and updates front pointer correctly.

2. Step 2: Check rear pointer update

   If queue becomes empty (front is null), rear must also be set to null but code misses this.

3. Final Answer:

   It does not update rear when queue becomes empty -> Option D

4. Quick Check:

   Rear must be null if front is null after dequeue = B [OK]

Hint: Set rear to null when front becomes null after dequeue [OK]

Common Mistakes:

• Ignoring rear pointer update on empty queue
• Assuming front check is enough
• Returning wrong value from dequeue

5. You want to implement a peek() method for your linked list queue that returns the front element without removing it. Which of the following implementations is correct?

hard

A. peek(): number | null { return this.front ? this.front.value : null; }

B. peek(): number | null { return this.rear ? this.rear.value : null; }

C. peek(): number | null { if (!this.front) throw new Error('Empty'); return this.front.next.value; }

D. peek(): number | null { return this.front.next ? this.front.next.value : null; }

Solution

1. Step 1: Understand peek purpose

   Peek returns front element value without removing it.

2. Step 2: Check each option

   A throws error and returns front.next value, wrong.
   B returns rear value, incorrect.
   C returns front value or null if empty, correct.
   D returns front.next value or null, wrong.

3. Final Answer:

   peek(): number | null { return this.front ? this.front.value : null; } -> Option A

4. Quick Check:

   Peek returns front value safely = C [OK]

Hint: Peek returns front value without changing queue [OK]

Common Mistakes:

• Returning rear value instead of front
• Accessing front.next without checking front
• Throwing error instead of returning null on empty