Enqueue Using Linked List in DSA C# - 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 added at the end of the linked list representing the queue.

Execution Sample

DSA C#

class Node {
  public int data;
  public Node next;
  public Node(int val) { data = val; next = null; }
}

class Queue {
  Node head, tail;
  public void Enqueue(int val) {
    Node newNode = new Node(val);
    if (tail == null) { head = tail = newNode; return; }
    tail.next = newNode;
    tail = newNode;
  }
}

This code adds a new element to the end of the queue using a linked list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node with value 10	None	newNode = Node(10)	null
2	Check if queue is empty (tail == null)	None	tail == null is True	null
3	Set head and tail to new node	10	head = newNode, tail = newNode	10 -> null
4	Create new node with value 20	10	newNode = Node(20)	10 -> null
5	Check if queue is empty (tail == null)	10	tail == null is False	10 -> null
6	Set tail.next to new node	10 -> 20	tail.next = newNode	10 -> 20 -> null
7	Update tail to new node	10 -> 20	tail = newNode	10 -> 20 -> null
8	Create new node with value 30	10 -> 20	newNode = Node(30)	10 -> 20 -> null
9	Check if queue is empty (tail == null)	10 -> 20	tail == null is False	10 -> 20 -> null
10	Set tail.next to new node	10 -> 20 -> 30	tail.next = newNode	10 -> 20 -> 30 -> null
11	Update tail to new node	10 -> 20 -> 30	tail = newNode	10 -> 20 -> 30 -> null
12	End of enqueue operations	10 -> 20 -> 30	No changes	10 -> 20 -> 30 -> null

💡 All enqueue operations completed; tail updated to last node; queue linked list updated.

Variable Tracker

Variable	Start	After Step 3	After Step 7	After Step 11	Final
head	null	Node(10)	Node(10)	Node(10)	Node(10)
tail	null	Node(10)	Node(20)	Node(30)	Node(30)
newNode	null	Node(10)	Node(20)	Node(30)	Node(30)
Linked List	empty	10 -> null	10 -> 20 -> null	10 -> 20 -> 30 -> null	10 -> 20 -> 30 -> null

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 execution_table row 2 and 3.

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. See execution_table rows 6 and 7.

What happens if we forget to update tail after adding a new node?

The tail pointer would still point to the old last node, breaking the queue's end. New nodes won't be added correctly. This is avoided by step 7 and 11.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what does the queue look like?

A null

B 10 -> null

C 10 -> 20 -> null

D 20 -> null

💡 Hint

Check the Visual State column at step 3 in execution_table.

At which step does the tail pointer first move from Node(10) to Node(20)?

A Step 7

B Step 3

C Step 6

D Step 11

💡 Hint

Look at Pointer Changes column for tail updates in execution_table.

If the queue was empty, which pointers are set to the new node during enqueue?

A Only head

B Only tail

C Both head and tail

D Neither head nor tail

💡 Hint

See execution_table step 3 where both head and tail are assigned.

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
- Update tail to new node
- Maintains FIFO order by adding at tail
- Visual: head -> ... -> tail -> null

Full Transcript

Enqueue operation in a queue using a linked list 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 linked to the new node, and then the tail pointer is updated to point to the new node. This process keeps the queue in FIFO order. The linked list grows by adding nodes at the tail, and the head remains at the front for dequeue operations.

Practice

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

easy

A. Adds an element at the front of the linked list

B. Removes an element from the front of the linked list

C. Deletes the last element of the linked list

D. Adds an element at the end of the linked list

Solution

1. Step 1: Understand enqueue operation

   Enqueue means adding an element to the queue.

2. Step 2: Identify linked list behavior for enqueue

   In a linked list queue, enqueue adds the new node at the end (tail).

3. Final Answer:

   Adds an element at the end of the linked list -> Option D

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 element at the front instead of the end
• Thinking enqueue removes elements

2. Which of the following is the correct syntax to create a new node and enqueue it in a linked list queue in C#?

easy

A. Node newNode = new Node(data); tail.next = newNode; tail = newNode;

B. Node newNode = Node(data); tail.next = newNode; tail = newNode;

C. Node newNode = new Node(); tail = newNode; tail.next = data;

D. Node newNode = new Node(data); head.next = newNode; head = newNode;

Solution

1. Step 1: Create new node with data

   Use 'new Node(data)' to create a node with the given data.

2. Step 2: Link new node at tail and update tail

   Set 'tail.next = newNode' and then update 'tail = newNode' to keep tail at last node.

3. Final Answer:

   Node newNode = new Node(data); tail.next = newNode; tail = newNode; -> Option A

4. Quick Check:

   Correct node creation and tail update [OK]

Hint: Use 'new' keyword and update tail pointer [OK]

Common Mistakes:

• Forgetting 'new' keyword when creating node
• Updating head instead of tail
• Assigning data to next pointer

3. What will be the state of the queue after executing the following C# code?

QueueLinkedList queue = new QueueLinkedList();
queue.Enqueue(10);
queue.Enqueue(20);
queue.Enqueue(30);

Assuming the queue prints elements from head to tail.

medium

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

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

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

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

Solution

1. Step 1: Enqueue 10, 20, 30 in order

   Each enqueue adds element at the tail, so order is 10, then 20, then 30.

2. Step 2: Print queue from head to tail

   Head points to 10, followed by 20, then 30, ending with null.

3. Final Answer:

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

4. Quick Check:

   Enqueue order preserved from head to tail [OK]

Hint: Enqueue adds at tail, print from head to tail [OK]

Common Mistakes:

• Reversing the order of elements
• Confusing head and tail pointers
• Assuming enqueue adds at head

4. Identify the error in the following enqueue method for a linked list queue in C#:

public void Enqueue(int data) {
    Node newNode = new Node(data);
    if (head == null) {
        head = newNode;
    } else {
        tail.next = newNode;
    }
}

medium

A. New node should be created outside the method

B. The tail pointer is not updated after adding new node

C. The head pointer should be updated instead of tail

D. The if condition should check tail instead of head

Solution

1. Step 1: Check tail update after enqueue

   After adding newNode at tail.next, tail must be updated to newNode.

2. Step 2: Identify missing tail update

   Code does not update tail, so tail still points to old last node, causing errors.

3. Final Answer:

   The tail pointer is not updated after adding new node -> Option B

4. Quick Check:

   Always update tail after enqueue [OK]

Hint: Update tail pointer after adding new node [OK]

Common Mistakes:

• Forgetting to update tail pointer
• Updating head instead of tail
• Creating node outside enqueue method

5. Given a linked list queue with elements 5 -> 15 -> 25 -> null, what will be the queue state after enqueueing 35 and then dequeueing one element?

hard

A. 25 -> 35 -> null

B. 5 -> 15 -> 25 -> 35 -> null

C. 15 -> 25 -> 35 -> null

D. 35 -> 5 -> 15 -> 25 -> null

Solution

1. Step 1: Enqueue 35 at tail

   Queue becomes 5 -> 15 -> 25 -> 35 -> null after enqueue.

2. Step 2: Dequeue removes from head

   Removing 5 from head leaves 15 -> 25 -> 35 -> null.

3. Final Answer:

   15 -> 25 -> 35 -> null -> Option C

4. Quick Check:

   Enqueue adds tail, dequeue removes head [OK]

Hint: Enqueue tail, dequeue head to update queue [OK]

Common Mistakes:

• Removing from tail instead of head
• Not updating head after dequeue
• Adding new element at head instead of tail