Enqueue Using Linked List in DSA C++ - Execution Trace

Concept Flow - Enqueue Using Linked List

Create new node with data

↓

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++

struct Node {
  int data;
  Node* next;
};

void enqueue(Node*& head, Node*& tail, int val) {
  Node* newNode = new Node{val, nullptr};
  if (!head) head = tail = newNode;
  else {
    tail->next = newNode;
    tail = newNode;
  }
}

This code adds a new node with value val to the end of the linked list queue.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node with data=10	None	newNode -> Node(10, nullptr)	null
2	Check if queue empty (head == nullptr)	None	head=nullptr, tail=nullptr	null
3	Queue empty, set head and tail to newNode	Node(10)	head -> Node(10), tail -> Node(10)	10 -> null
4	Create new node with data=20	Node(10)	newNode -> Node(20, nullptr)	10 -> null
5	Queue not empty, set tail->next to newNode	Node(10) -> Node(20)	tail->next = newNode	10 -> 20 -> null
6	Update tail to newNode	Node(10) -> Node(20)	tail -> Node(20)	10 -> 20 -> null
7	Create new node with data=30	Node(10) -> Node(20)	newNode -> Node(30, nullptr)	10 -> 20 -> null
8	Queue not empty, set tail->next to newNode	Node(10) -> Node(20) -> Node(30)	tail->next = newNode	10 -> 20 -> 30 -> null
9	Update tail to newNode	Node(10) -> Node(20) -> Node(30)	tail -> Node(30)	10 -> 20 -> 30 -> null
10	Stop	Node(10) -> Node(20) -> Node(30)	No changes	10 -> 20 -> 30 -> null

💡 No more enqueue operations, queue has three nodes.

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	Final
head	nullptr	Node(10)	Node(10)	Node(10)	Node(10)
tail	nullptr	Node(10)	Node(20)	Node(30)	Node(30)
newNode	nullptr	Node(10)	Node(20)	Node(30)	nullptr (no new node)
List Size	0	1	2	3	3

Key Moments - 3 Insights

Why do we check if the queue is empty before adding a new node?

Because if the queue is empty (head is nullptr), both head and tail must point to the new node. This is shown in step 3 where head and tail are set to the new node.

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 5 and 6.

What happens if we forget to update tail after enqueue?

The tail pointer would still point to the old last node, breaking the queue's end. New nodes would not be added correctly. This is why step 6 and 9 are important.

Visual Quiz - 3 Questions

Look at the execution table, what is the visual state after step 6?

A 10 -> 20 -> null

B 10 -> 20 -> 30 -> null

C 10 -> null

D null

💡 Hint

Check the Visual State column at step 6 in the execution_table.

At which step does the tail pointer first move to a new node after initialization?

A Step 3

B Step 9

C Step 6

D Step 2

💡 Hint

Look at the Pointer Changes column for tail updates in the execution_table.

If the queue was initially empty, what pointers are set when the first node is enqueued?

A Only tail is set to new node

B Both head and tail are set to new node

C Only head is set to new node

D Neither head nor tail is set

💡 Hint

Refer to step 3 in the execution_table where head and tail are assigned.

Concept Snapshot

Enqueue Using Linked List:
- Create new node with data and next=nullptr
- If queue empty (head==nullptr), set head and tail to new node
- Else, set tail->next to new node and update tail to new node
- New node always added at the end
- Tail always points to last node

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 data and next pointer set to null. 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 tail is updated to point to the new node. This maintains the queue order and ensures efficient addition at the end. The execution table shows step-by-step how nodes are added and pointers updated, with the visual state of the linked list after each step.

Practice

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

easy

A. Adds an element at the end (rear) of the linked list

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

C. Deletes the entire linked list

D. Adds an element at the front (head) of the linked list

Solution

1. Step 1: Understand enqueue operation in queue

   Enqueue means adding an element to the queue.

2. Step 2: Identify linked list position for enqueue

   In a linked list queue, enqueue adds at the rear (end) to maintain FIFO order.

3. Final Answer:

   Adds an element at the end (rear) of the linked list -> Option A

4. Quick Check:

   Enqueue = Add at rear [OK]

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

Common Mistakes:

• Confusing enqueue with dequeue operation
• Adding element at front instead of rear
• 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* temp = Node(data); rear->next = temp; rear = temp;

B. Node temp = new Node(data); rear->next = temp; rear = temp;

C. Node* temp = new Node(data); rear->next = temp; rear = temp;

D. Node* temp = new Node; rear->next = temp; rear = temp;

Solution

1. Step 1: Check node creation syntax in C++

   Correct way to create a node dynamically is Node* temp = new Node(data);.

2. Step 2: Verify linking and updating rear pointer

   Link new node by rear->next = temp; and update rear to new node rear = temp;.

3. Final Answer:

   Node* temp = new Node(data); rear->next = temp; rear = temp; -> Option C

4. Quick Check:

   Use new with pointer and update rear [OK]

Hint: Use 'new' keyword and pointer for node creation [OK]

Common Mistakes:

• Not using pointer (*) for node
• Missing 'new' keyword for dynamic allocation
• Incorrect assignment without pointers

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. 30 -> 20 -> 10 -> null

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

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

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

Solution

1. Step 1: Enqueue 10 on empty queue

   Queue becomes 10 -> null.

2. Step 2: Enqueue 20 and 30 sequentially

   Adding 20 at rear: 10 -> 20 -> null; then 30 at rear: 10 -> 20 -> 30 -> null.

3. Final Answer:

   10 -> 20 -> 30 -> null -> Option B

4. Quick Check:

   FIFO order maintained: 10, 20, 30 [OK]

Hint: Enqueue adds at rear, order stays same [OK]

Common Mistakes:

• Reversing order of elements
• Confusing enqueue with push front
• Ignoring null termination

4. Identify the error in the following enqueue function for a linked list queue:

void enqueue(int data) {
  Node* temp = new Node(data);
  if (rear == nullptr) {
    front = temp;
  } else {
    rear->next = temp;
  }
  // Missing update of rear pointer here
}

medium

A. rear pointer is not updated to the new node

B. front pointer should be updated to temp always

C. Node creation syntax is incorrect

D. next pointer of temp should be set to front

Solution

1. Step 1: Check rear pointer update after enqueue

   rear pointer must point to the newly added node to keep track of queue end.

2. Step 2: Identify missing update in code

   Code misses rear = temp; after linking new node.

3. Final Answer:

   rear pointer is not updated to the new node -> Option A

4. Quick Check:

   rear must update to new node [OK]

Hint: Always update rear to new node after enqueue [OK]

Common Mistakes:

• Forgetting to update rear pointer
• Updating front pointer incorrectly
• Setting next pointer wrongly

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. 35 -> 5 -> 15 -> 25 -> null

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

C. 25 -> 35 -> null

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

Solution

1. Step 1: Enqueue 35 at rear

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

2. Step 2: Dequeue removes front element 5

   After dequeue, front moves to 15, so queue is 15 -> 25 -> 35 -> null.

3. Final Answer:

   15 -> 25 -> 35 -> null -> Option D

4. Quick Check:

   Enqueue rear, dequeue front; update pointers accordingly [OK]

Hint: Enqueue rear, dequeue front; update pointers accordingly [OK]

Common Mistakes:

• Removing wrong element on dequeue
• Not updating front pointer after dequeue
• Adding new element at front instead of rear