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 created and added at the end of the linked list representing the queue.

Execution Sample

DSA C

void enqueue(int data) {
  Node* newNode = malloc(sizeof(Node));
  newNode->data = data;
  newNode->next = NULL;
  if (tail == NULL) {
    head = tail = newNode;
  } else {
    tail->next = newNode;
    tail = newNode;
  }
}

This code adds a new element at 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 data=10	None	newNode created	null
2	Check if queue empty (tail == NULL)	None	tail is NULL	null
3	Set head and tail to newNode	10	head -> newNode, tail -> newNode	10 -> null
4	Create new node with data=20	10	newNode created	10 -> null
5	Check if queue empty (tail == NULL)	10	tail is not NULL	10 -> null
6	Set tail->next to newNode	10, 20	tail->next -> newNode	10 -> 20 -> null
7	Update tail to newNode	10, 20	tail -> newNode	10 -> 20 -> null
8	Create new node with data=30	10, 20	newNode created	10 -> 20 -> null
9	Check if queue empty (tail == NULL)	10, 20	tail is not NULL	10 -> 20 -> null
10	Set tail->next to newNode	10, 20, 30	tail->next -> newNode	10 -> 20 -> 30 -> null
11	Update tail to newNode	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 points to last node; list updated accordingly.

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)
List Size	0	1	2	3	3

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

Why do we update tail->next before moving tail to newNode?

We must link the current last node's next pointer to the new node before updating tail, so the list stays connected. See steps 6 and 7 in execution_table.

What happens if we forget to set newNode->next to NULL?

The new node might point to garbage or old data, breaking the list. The code sets newNode->next = NULL at step 1 and 4 and 8 to avoid this.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what does head point to?

A NULL

B Node with data 10

C Node with data 20

D Node with data 30

💡 Hint

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

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

A Step 3

B Step 6

C Step 7

D Step 10

💡 Hint

Look at the 'Pointer Changes' column for tail updates.

If we enqueue a new node with data=40 after step 11, what will tail point to?

A Node with data 40

B Node with data 30

C Node with data 20

D NULL

💡 Hint

Tail always points to the last node added, see steps 7 and 11.

Concept Snapshot

Enqueue Using Linked List:
- Create new node with data and next=NULL
- If queue empty (tail==NULL), set head and tail to new node
- Else, set tail->next to new node and update tail
- Tail always points to last node
- List grows by adding nodes at tail end

Full Transcript

Enqueue operation in a linked list queue involves creating a new node 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 process ensures the queue grows at the tail end, maintaining FIFO order. The execution table shows each step with pointer updates and the visual linked list state. Key moments clarify why checking tail for NULL is important, why tail->next must be updated before tail, and why newNode->next must be NULL to avoid list corruption.

Practice

1. What does the enqueue operation do in a queue implemented using a linked list?

easy

A. Deletes the entire queue

B. Adds an element at the end (rear) of the queue

C. Checks if the queue is empty

D. Removes an element from the front of the queue

Solution

1. Step 1: Understand enqueue operation

   Enqueue means adding a new element to the queue.

2. Step 2: Identify position of insertion in linked list queue

   In a linked list queue, new elements are added at the rear (end) to maintain order.

3. Final Answer:

   Adds an element at the end (rear) of the queue -> Option B

4. Quick Check:

   Enqueue = Add at rear [OK]

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

Common Mistakes:

• Confusing enqueue with dequeue operation
• Thinking enqueue adds at the front
• Mixing queue with stack operations

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

easy

A. newNode = malloc(sizeof(Node));

B. struct Node newNode = (struct Node*)malloc(sizeof(struct Node));

C. Node newNode = malloc(sizeof(Node));

D. struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

Solution

1. Step 1: Allocate memory for new node

   In C, use malloc with sizeof(struct Node) to allocate memory.

2. Step 2: Correct pointer declaration and casting

   Declare pointer as struct Node* and cast malloc result to (struct Node*).

3. Final Answer:

   struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); -> Option D

4. Quick Check:

   Correct malloc syntax = struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); [OK]

Hint: Always cast malloc to (struct Node*) in C [OK]

Common Mistakes:

• Missing struct keyword in declaration
• Not casting malloc result
• Using wrong variable types

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

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

struct Node* front = NULL;
struct Node* rear = NULL;

// Enqueue 10
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = 10;
newNode->next = NULL;
if (rear == NULL) {
  front = rear = newNode;
} else {
  rear->next = newNode;
  rear = newNode;
}

// Enqueue 20
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = 20;
newNode->next = NULL;
rear->next = newNode;
rear = newNode;

medium

A. 10 -> NULL

B. 20 -> 10 -> NULL

C. 10 -> 20 -> NULL

D. 20 -> NULL

Solution

1. Step 1: Enqueue 10 when queue is empty

   Both front and rear point to new node with data 10.

2. Step 2: Enqueue 20 when queue has one element

   rear->next points to new node with data 20, rear moves to this node.

3. Final Answer:

   10 -> 20 -> NULL -> Option C

4. Quick Check:

   Order of enqueue = 10 then 20 [OK]

Hint: New nodes link at rear, order stays FIFO [OK]

Common Mistakes:

• Reversing order of nodes
• Not updating rear pointer
• Forgetting to set next to NULL

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

void enqueue(int value) {
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
  newNode->data = value;
  newNode->next = NULL;
  if (front == NULL) {
    front = newNode;
  } else {
    rear->next = newNode;
    rear = newNode;
  }
}

medium

A. rear pointer is not updated when queue is empty

B. newNode->next should point to front

C. malloc size is incorrect

D. front pointer is updated incorrectly

Solution

1. Step 1: Check rear pointer update when queue is empty

   When front is NULL, only front = newNode is executed, rear remains uninitialized.

2. Step 2: No rear update in if branch

   The else block sets rear = newNode, but it is skipped when queue is empty.

3. Final Answer:

   rear pointer is not updated when queue is empty -> Option A

4. Quick Check:

   rear must be set when queue is empty [OK]

Hint: Always update rear when queue was empty [OK]

Common Mistakes:

• Not setting rear when queue is empty
• Incorrect next pointer assignment
• Wrong malloc size or casting

5. Given a linked list queue with elements 5 -> 15 -> 25 -> NULL, what will be the queue after enqueueing 35 and then 45? Show the final linked list state.

hard

A. 5 -> 15 -> 25 -> 35 -> 45 -> NULL

B. 45 -> 35 -> 25 -> 15 -> 5 -> NULL

C. 5 -> 15 -> 25 -> NULL

D. 35 -> 45 -> 5 -> 15 -> 25 -> NULL

Solution

1. Step 1: Understand enqueue adds at rear

   Enqueue adds new nodes at the end of the queue to maintain order.

2. Step 2: Add 35 and then 45 at the rear

   After adding 35, queue becomes 5 -> 15 -> 25 -> 35 -> NULL. Then adding 45 results in 5 -> 15 -> 25 -> 35 -> 45 -> NULL.

3. Final Answer:

   5 -> 15 -> 25 -> 35 -> 45 -> NULL -> Option A

4. Quick Check:

   Enqueue order preserved at rear [OK]

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

Common Mistakes:

• Adding new nodes at front instead of rear
• Reversing the order of elements
• Not updating rear pointer after enqueue