Insert at End Tail Insert in DSA C - Execution Trace

Concept Flow - Insert at End Tail Insert

Create new node with data

↓

Is list empty?

↓

Set head = new

↓

Traverse until current.next == NULL

↓

Set current.next = new node

↓

Done

Create a new node, check if list is empty, if yes set head to new node; else traverse to last node and link new node at end.

Execution Sample

DSA C

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

void insertAtEnd(struct Node** head, int val) {
  // Insert val at list end
  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
  new_node->data = val;
  new_node->next = NULL;

  if (*head == NULL) {
    *head = new_node;
    return;
  }

  struct Node* current = *head;
  while (current->next != NULL) {
    current = current->next;
  }
  current->next = new_node;
}

Insert a new node with given value at the end of a singly linked list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node with data=10	∅	new_node created with data=10, next=∅	∅
2	Check if head == NULL	∅	head == NULL (list empty)	∅
3	Set head = new_node	10	head → new_node	┌────────┐ │ data:10│ │ next:∅ │ └────────┘ head
4	Create new node with data=20	10	new_node created with data=20, next=∅	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ next:∅ │ │ next:∅ │ └────────┘ └────────┘ head
5	Check if head == NULL	10	head != NULL (list not empty)	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ next:∅ │ │ next:∅ │ └────────┘ └────────┘ head
6	Traverse to last node (current = head)	10	current → node with data=10	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ next:∅ │ │ next:∅ │ └────────┘ └────────┘ head new_node
7	Check current.next == NULL	10	current.next == NULL (true)	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ next:∅ │ │ next:∅ │ └────────┘ └────────┘ head new_node
8	Set current.next = new_node	10 -> 20	node 10.next → new_node	┌────────┐ ┌────────┐ │ data:10│───→│ data:20│ │ next:──┼ │ next:∅ │ └────────┘ └────────┘ head ✓ tail
9	Done	10 -> 20	No pointer changes	┌────────┐ ┌────────┐ │ data:10│───→│ data:20│ │ next:──┼ │ next:∅ │ └────────┘ └────────┘ head tail

💡 Traversal ends when current.next is NULL; new node linked as last node.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 4	After Step 6	After Step 8	Final
head	NULL	NULL	points to node 10	points to node 10	points to node 10	points to node 10	points to node 10
new_node	NULL	node 10	node 10	node 20	node 20	node 20	node 20
current	NULL	NULL	NULL	NULL	node 10	node 10	node 10

Key Moments - 3 Insights

Why do we check if head == NULL before inserting?

Because if the list is empty (head == NULL), we must set head to the new node directly (see step 2 and 3 in execution_table). Otherwise, we traverse the list.

Why do we stop traversal when current.next == NULL, not current == NULL?

Because current.next == NULL means current is the last node. We want to link the new node after current. If we checked current == NULL, we would go past the last node (see step 7).

What pointer changes when we insert the new node at the end?

The last node's next pointer changes from NULL to point to the new node (see step 8). The new node's next remains NULL.

Visual Quiz - 3 Questions

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

A The new node with data 10

B NULL

C The new node with data 20

D The last node in the list

💡 Hint

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

At which step does the traversal stop before inserting the new node?

A Step 5

B Step 6

C Step 7

D Step 8

💡 Hint

Look for the step where current.next == NULL is true in the execution_table.

If the list was empty, which step sets the head pointer?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

See where head is assigned to new_node in the execution_table.

Concept Snapshot

Insert at End (Tail Insert) in Linked List:
- Create new node with data and next = NULL
- If list empty (head == NULL), set head = new node
- Else traverse list until last node (current.next == NULL)
- Set last node's next = new node
- New node becomes new tail with next = NULL

Full Transcript

This concept shows how to insert a new node at the end of a singly linked list. First, a new node is created with the given data and its next pointer set to NULL. Then, we check if the list is empty by seeing if head is NULL. If empty, we set head to the new node. If not empty, we start from head and traverse nodes until we find the last node whose next pointer is NULL. We then set that last node's next pointer to the new node, effectively adding it at the end. The new node's next remains NULL, marking it as the new tail. This process ensures the list grows by adding nodes at the end.

Practice

1. What does the 'Insert at End' operation do in a singly linked list?

easy

A. Adds a new node at the end (tail) of the list

B. Deletes the last node of the list

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

D. Searches for a node at the end of the list

Solution

1. Step 1: Understand the operation

   Inserting at the end means adding a new node after the current last node.

2. Step 2: Identify the effect on the list

   The new node becomes the new tail, extending the list by one node.

3. Final Answer:

   Adds a new node at the end (tail) of the list -> Option A

4. Quick Check:

   Insert at end = Add node at tail [OK]

Hint: Insert at end means add after last node [OK]

Common Mistakes:

• Confusing insert at end with insert at beginning
• Thinking it deletes a node
• Assuming it searches instead of inserts

2. Which of the following is the correct syntax to create a new node in C for tail insertion?

easy

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

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

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

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

Solution

1. Step 1: Understand node creation in C

   We use malloc to allocate memory and cast it to pointer of struct Node.

2. Step 2: Check syntax correctness

   struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); correctly casts malloc result to (struct Node*) and uses sizeof(struct Node).

3. Final Answer:

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

4. Quick Check:

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

Hint: Use malloc with (struct Node*) cast for new node [OK]

Common Mistakes:

• Missing cast to (struct Node*)
• Using wrong type without struct keyword
• Assigning malloc to struct variable instead of pointer

3. What will be the output linked list after inserting 4 at the end of the list 1 -> 2 -> 3 -> NULL using tail insertion?

medium

A. 1 -> 2 -> 3 -> NULL

B. 1 -> 2 -> 3 -> 4 -> NULL

C. 1 -> 2 -> 4 -> 3 -> NULL

D. 4 -> 1 -> 2 -> 3 -> NULL

Solution

1. Step 1: Understand tail insertion effect

   Inserting 4 at the end adds it after 3, the current tail.

2. Step 2: Visualize the new list

   The list becomes 1 -> 2 -> 3 -> 4 -> NULL after insertion.

3. Final Answer:

   1 -> 2 -> 3 -> 4 -> NULL -> Option B

4. Quick Check:

   Insert 4 at tail = 1->2->3->4->NULL [OK]

Hint: New node goes after last node, not at front [OK]

Common Mistakes:

• Inserting at head instead of tail
• Placing new node in middle
• Not updating tail pointer

4. Given the following code snippet for tail insertion, what is the error?

void insertAtEnd(struct Node** head, int data) {
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
  newNode->data = data;
  newNode->next = NULL;
  if (*head == NULL) {
    *head = newNode;
  } else {
    struct Node* temp = *head;
    while (temp->next != NULL) {
      temp = temp->next;
    }
    temp = newNode;
  }
}

medium

A. temp = newNode; does not link newNode to the list

B. Missing malloc for newNode

C. newNode->next should not be NULL

D. Head pointer is not updated when list is empty

Solution

1. Step 1: Analyze the while loop and insertion

   The code moves temp to last node, but then does temp = newNode; which only changes temp pointer.

2. Step 2: Identify correct linking

   To link newNode, temp->next should be assigned newNode, not temp itself.

3. Final Answer:

   temp = newNode; does not link newNode to the list -> Option A

4. Quick Check:

   Link newNode by temp->next = newNode [OK]

Hint: Assign newNode to temp->next, not temp [OK]

Common Mistakes:

• Assigning newNode to temp pointer instead of temp->next
• Forgetting to set newNode->next to NULL
• Not handling empty list case

5. You have a singly linked list with nodes 10 -> 20 -> 30 -> NULL. You want to insert 40 at the end using tail insertion. Which of the following code snippets correctly performs this insertion and updates the list?

hard

A. struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));\nnewNode->data = 40;\nnewNode->next = NULL;\nhead = newNode;

B. struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));\nnewNode->data = 40;\nnewNode->next = head;\nhead = newNode;

C. struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));\nnewNode->data = 40;\nnewNode->next = NULL;\nstruct Node* temp = head;\nwhile(temp->next != NULL) { temp = temp->next; }\ntemp->next = newNode;

D. struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));\nnewNode->data = 40;\nnewNode->next = NULL;\nstruct Node* temp = head;\nwhile(temp != NULL) { temp = temp->next; }\ntemp->next = newNode;

Solution

1. Step 1: Create new node with data 40 and next NULL

   This prepares the new node to be added at the end.

2. Step 2: Traverse list to last node

   Using while(temp->next != NULL) moves temp to last node (30).

3. Step 3: Link last node's next to newNode

   temp->next = newNode correctly attaches new node at end.

4. Final Answer:

   Traverse to last node with while(temp->next != NULL), then temp->next = newNode -> Option C

5. Quick Check:

   Traverse to tail, then temp->next = newNode [OK]

Hint: Traverse to last node, then link new node at next [OK]

Common Mistakes:

• Setting newNode->next to head (inserts at front)
• Not updating last node's next pointer
• Loop condition allowing temp to become NULL