Enqueue Using Linked List in DSA Typescript - Execution Trace

Concept Flow - Enqueue Using Linked List

Create new node with value

↓

Is queue empty?

Yes→Set head and tail to new node

No↓

Set tail.next to new node

↓

Update tail to new node

↓

Done

This flow shows how a new node is created and added at the end of the linked list queue, updating pointers accordingly.

Execution Sample

DSA Typescript

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

class Queue {
  head: Node | null = null;
  tail: Node | null = null;

  enqueue(value: number) {
    const newNode = new Node(value);
    if (!this.tail) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
  }
}

This code adds a new value to the end of a linked list queue by creating a new node and updating head and tail pointers.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Enqueue 10 (empty queue)	10	head -> 10, tail -> 10	10 -> null
2	Enqueue 20	10 -> 20	tail.next -> 20, tail -> 20	10 -> 20 -> null
3	Enqueue 30	10 -> 20 -> 30	tail.next -> 30, tail -> 30	10 -> 20 -> 30 -> null
4	Stop	No more enqueues	No pointer changes	10 -> 20 -> 30 -> null

💡 No more enqueue operations, queue contains 3 nodes.

Variable Tracker

Variable	Start	After 1	After 2	After 3	Final
head	null	Node(10)	Node(10)	Node(10)	Node(10)
tail	null	Node(10)	Node(20)	Node(30)	Node(30)
newNode	N/A	Node(10)	Node(20)	Node(30)	N/A

Key Moments - 3 Insights

Why do we check if tail is null before adding a new node?

Because if tail is null, the queue is empty, so both head and tail must point to the new node. This is shown in step 1 of the execution_table where head and tail are set to Node(10).

Why do we update tail.next before moving tail to the new node?

Updating tail.next links the current last node to the new node, maintaining the chain. Then tail moves to the new node to mark the new end. This happens in steps 2 and 3 in the execution_table.

What does the visual state '10 -> 20 -> 30 -> null' represent?

It shows the linked list nodes in order from head to tail, with 'null' marking the end. This helps visualize the queue's contents after each enqueue.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what does tail point to after enqueueing 20?

A Node with value 10

B Node with value 30

C Node with value 20

D null

💡 Hint

Check the 'Pointer Changes' column at step 2 in the execution_table.

At which step does the queue change from empty to having nodes?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the 'Operation' and 'Pointer Changes' columns in the execution_table.

If we enqueue a new node when tail is null, what happens to head?

A Head remains null

B Head points to the new node

C Head points to the old tail

D Head points to null

💡 Hint

Refer to step 1 in the execution_table and variable_tracker for head changes.

Concept Snapshot

Enqueue Using Linked List:
- Create new node with value
- If queue empty (tail null), set head and tail to new node
- Else, set tail.next to new node and update tail
- New node becomes new tail
- Visual: head -> ... -> tail -> null

Full Transcript

Enqueue operation in a linked list queue adds a new node at the end. First, a new node is created with the given value. If the queue is empty, both head and tail pointers are set to this new node. Otherwise, the current tail's next pointer is set to the new node, and then tail is updated to point to the new node. This maintains the linked list structure with head at the front and tail at the end. The visual state shows the nodes connected with arrows ending in null. This process repeats for each enqueue operation, growing the queue by one node each time.

Practice

1. What does the enqueue operation do in a linked list implementation of a queue?

easy

A. Removes the first element from the linked list

B. Adds a new element at the end (tail) of the linked list

C. Adds a new element at the beginning (head) of the linked list

D. Deletes the last element from the linked list

Solution

1. Step 1: Understand enqueue operation

   Enqueue means adding an element to the queue.

2. Step 2: Identify linked list position for enqueue

   In a linked list queue, new elements are added at the tail (end).

3. Final Answer:

   Adds a new element at the end (tail) of the linked list -> Option B

4. Quick Check:

   Enqueue = Add at tail [OK]

Hint: Enqueue always adds at the tail in linked list queue [OK]

Common Mistakes:

• Confusing enqueue with dequeue operation
• Adding new element at head instead of tail
• Thinking enqueue removes elements
• Mixing linked list positions

2. Which of the following is the correct TypeScript syntax to create a new node for enqueue in a linked list?

easy

A. newNode = new Node();

B. let newNode = Node(value);

C. const newNode = new Node(value);

D. const newNode = Node.new(value);

Solution

1. Step 1: Recall TypeScript class instantiation

   To create an object, use new ClassName(params).

2. Step 2: Check options for correct syntax

   Only const newNode = new Node(value); correctly creates a new Node instance.

3. Final Answer:

   const newNode = new Node(value); -> Option C

4. Quick Check:

   Use 'new' keyword to instantiate class [OK]

Hint: Use 'new' keyword to create class instances in TypeScript [OK]

Common Mistakes:

• Omitting 'new' keyword when creating objects
• Using function call syntax without 'new'
• Incorrect property access like Node.new
• Not declaring variable with let or const

3. What will be the state of the queue after executing the following enqueue operations on an empty linked list queue?

enqueue(10); enqueue(20); enqueue(30);

medium

A. 10 -> 20 -> 30 -> null

B. 30 -> 20 -> 10 -> null

C. null -> 10 -> 20 -> 30

D. 20 -> 10 -> 30 -> null

Solution

1. Step 1: Understand enqueue order

   Enqueue adds elements at the tail, so order is preserved as inserted.

2. Step 2: Trace each enqueue

   After enqueue(10): 10 -> null
   After enqueue(20): 10 -> 20 -> null
   After enqueue(30): 10 -> 20 -> 30 -> null

3. Final Answer:

   10 -> 20 -> 30 -> null -> Option A

4. Quick Check:

   Enqueue order = insertion order [OK]

Hint: Enqueue adds at tail, so order stays same as insertion [OK]

Common Mistakes:

• Reversing order of elements after enqueue
• Confusing enqueue with push at head
• Misreading linked list direction
• Ignoring null at the end

4. Consider this enqueue function snippet for a linked list queue:

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

What is the bug in this code?

medium

A. It does not update the previous tail's next pointer to newNode

B. It incorrectly sets head to null when queue is empty

C. It creates newNode without value

D. It sets tail to null after enqueue

Solution

1. Step 1: Analyze enqueue logic

   When queue is empty, head and tail should point to newNode.

2. Step 2: Check linking of nodes

   Code sets tail = newNode but does not link old tail's next to newNode, breaking chain.

3. Final Answer:

   It does not update the previous tail's next pointer to newNode -> Option A

4. Quick Check:

   Link old tail's next to newNode [OK]

Hint: Always link old tail's next to new node when enqueueing [OK]

Common Mistakes:

• Forgetting to update old tail's next pointer
• Not handling empty queue case properly
• Setting tail to null accidentally
• Creating node without value parameter

5. You have a linked list queue with elements: 5 -> 15 -> 25 -> null.
After enqueue(35), what will be the correct linked list representation and tail node value?

hard

A. 5 -> 15 -> 25 -> 35 -> null, tail value = 25

B. 35 -> 5 -> 15 -> 25 -> null, tail value = 25

C. 5 -> 15 -> 25 -> null, tail value = 25

D. 5 -> 15 -> 25 -> 35 -> null, tail value = 35

Solution

1. Step 1: Understand enqueue effect on queue

   Enqueue adds new element at tail, so 35 goes after 25.

2. Step 2: Update tail pointer

   Tail must point to the new last node, which holds 35.

3. Final Answer:

   5 -> 15 -> 25 -> 35 -> null, tail value = 35 -> Option D

4. Quick Check:

   Enqueue adds at tail, tail updates to new node [OK]

Hint: Tail always points to last enqueued node [OK]

Common Mistakes:

• Adding new node at head instead of tail
• Not updating tail pointer after enqueue
• Confusing tail value with head value
• Leaving tail pointing to old last node