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 node

↓

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;
  Node* next;
};

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

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	∅	newNode → Node(10, next=∅)	List empty
2	Check if head is null	∅	head = ∅	List empty
3	Set head = newNode	10	head → Node(10, next=∅)	┌────────┐ │ data:10│ │ next:∅ │ └────────┘ head
4	Create new node with data=20	10	newNode → Node(20, next=∅)	List has 1 node
5	Check if head is null	10	head → Node(10, next=∅)	List not empty
6	Traverse from head to last node	10	current → Node(10, next=∅)	At node 10
7	Set current.next = newNode	10 -> 20	Node(10).next → Node(20, next=∅)	┌────────┐ ┌────────┐ │ data:10│ ──→ │ data:20│ │ next:──┼──── │ next:∅ │ └────────┘ └────────┘ head
8	Create new node with data=30	10 -> 20	newNode → Node(30, next=∅)	List has 2 nodes
9	Traverse from head to last node	10 -> 20	current → Node(10, next=Node(20))	At node 10
10	Move current to next node	10 -> 20	current → Node(20, next=∅)	At node 20
11	Set current.next = newNode	10 -> 20 -> 30	Node(20).next → Node(30, next=∅)	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ ──→ │ data:20│ ──→ │ data:30│ │ next:──┼──── │ next:──┼──── │ next:∅ │ └────────┘ └────────┘ └────────┘ head
12	End of insertions	10 -> 20 -> 30	No pointer changes	Final list state

💡 Traversal stops when current.next is null, new node linked at end.

Variable Tracker

Variable	Start	After Step 3	After Step 7	After Step 11	Final
head	∅	Node(10)	Node(10)	Node(10)	Node(10)
newNode	∅	Node(20)	Node(20)	Node(30)	Node(30)
current	∅	∅	Node(10)	Node(20)	∅
List Size	0	1	2	3	3

Key Moments - 3 Insights

Why do we check if head is null before traversal?

Because if head is null, the list is empty and we must set head to the new node directly (see step 2 and 3). Otherwise, traversal would fail.

Why does traversal stop when current.next is null, not current?

Because current.next being null means current is the last node. We want to link the new node after the last node (see step 6 and 10).

What happens to the old last node's next pointer after insertion?

It changes from null to point to the new node, linking the new node at the end (see step 7 and 11 pointer changes).

Visual Quiz - 3 Questions

Look at the execution table at step 7, what does the pointer Node(10).next point to?

A null

B Node(20)

C Node(30)

D head

💡 Hint

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

At which step does the list first contain three nodes?

A Step 3

B Step 7

C Step 11

D Step 12

💡 Hint

Look at the 'Nodes in List' column to see when three nodes appear.

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

A Step 3

B Step 1

C Step 2

D Step 6

💡 Hint

Refer to the 'Pointer Changes' and 'Operation' columns around step 3.

Concept Snapshot

Insert at End (Tail Insert) in singly linked list:
- Create new node with data and next=null
- If list empty (head=null), set head=new node
- Else traverse from head to last node (where next=null)
- Set last node's next to new node
- New node becomes new tail
- Time complexity: O(n) for traversal

Full Transcript

This visual trace 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. If the list is empty (head is null), the head pointer is set to this new node. Otherwise, we start from the head and traverse the list until we find the last node whose next pointer is null. Then, we set that last node's next pointer to the new node, effectively adding it at the end. The variable tracker shows how pointers and list size change after each insertion. Key moments clarify why we check for empty list before traversal and why traversal stops at current.next being null. The visual quiz tests understanding of pointer changes and list size during insertion.

Practice

1. What does the "Insert at End (Tail Insert)" operation do in a singly linked list?

easy

A. Adds a new node at the end of the list

B. Adds a new node at the beginning of the list

C. Deletes the last node of the list

D. Deletes the first node of the list

Solution

1. Step 1: Understand the operation

   Insert at End means adding a new node after the last node in the list.

2. Step 2: Compare with other operations

   Adding at the beginning is different; deleting nodes removes them, not adds.

3. Final Answer:

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

4. Quick Check:

   Insert at End = Add node at list's tail [OK]

Hint: Tail insert always adds node after last element [OK]

Common Mistakes:

• Confusing tail insert with head insert
• Thinking it deletes nodes
• Assuming it inserts in the middle

2. Which of the following is the correct syntax to create a new node and insert it at the end of a singly linked list 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 = Node(data); tail->next = newNode; tail = newNode;

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

Solution

1. Step 1: Create a new node using pointer and dynamic allocation

   In C++, new nodes are created with 'new' keyword returning a pointer: Node* newNode = new Node(data);

2. Step 2: Link the new node to the current tail and update tail pointer

   Set tail->next = newNode; then update tail = newNode;

3. Final Answer:

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

4. Quick Check:

   Use pointer and new keyword for node creation [OK]

Hint: Use 'new' and pointers to create nodes in C++ [OK]

Common Mistakes:

• Not using pointers for new nodes
• Missing 'new' keyword causing errors
• Assigning object instead of pointer

3. What will be the output linked list after executing the following code?

struct Node {
  int data;
  Node* next;
  Node(int val) : data(val), next(nullptr) {}
};

Node* head = new Node(1);
Node* tail = head;

// Insert 2 at end
Node* newNode = new Node(2);
tail->next = newNode;
tail = newNode;

// Insert 3 at end
newNode = new Node(3);
tail->next = newNode;
tail = newNode;

// Print list
Node* temp = head;
while(temp != nullptr) {
  std::cout << temp->data << " -> ";
  temp = temp->next;
}
std::cout << "null";

medium

A. 1 -> 3 -> 2 -> null

B. 3 -> 2 -> 1 -> null

C. null

D. 1 -> 2 -> 3 -> null

Solution

1. Step 1: Trace node insertions

   Start with head = 1. Insert 2 at end: list is 1 -> 2. Insert 3 at end: list is 1 -> 2 -> 3.

2. Step 2: Trace print loop

   Prints nodes in order: 1, 2, 3, then prints 'null'.

3. Final Answer:

   1 -> 2 -> 3 -> null -> Option D

4. Quick Check:

   Tail insert appends nodes in order [OK]

Hint: Tail insert keeps order of insertion [OK]

Common Mistakes:

• Confusing order of nodes
• Not updating tail pointer
• Printing reversed list

4. Identify the error in the following code snippet for inserting a node at the end of a singly linked list:

Node* newNode = new Node(5);
tail = newNode;
tail->next = nullptr;

medium

A. The new node should be created without 'new'

B. The new node is not linked to the previous tail's next pointer

C. The new node should not have next set to nullptr

D. The tail pointer should not be updated

Solution

1. Step 1: Check linking of new node

   New node is created but previous tail's next is not updated to point to newNode.

2. Step 2: Understand tail update

   Updating tail pointer before linking breaks the chain; list loses connection to new node.

3. Final Answer:

   The new node is not linked to the previous tail's next pointer -> Option B

4. Quick Check:

   Always link previous tail's next before updating tail [OK]

Hint: Link old tail's next before moving tail pointer [OK]

Common Mistakes:

• Updating tail before linking new node
• Forgetting to set previous tail's next
• Misordering pointer assignments

5. You have a singly linked list with only a head pointer (no tail pointer). Which of the following is the most efficient way to insert a new node at the end of the list?

hard

A. Traverse the entire list to find the last node, then insert the new node after it

B. Insert the new node at the head and then swap data with the last node

C. Create a tail pointer and update it during every insertion to avoid traversal

D. Insert the new node at the beginning and reverse the list

Solution

1. Step 1: Analyze insertion without tail pointer

   Without tail pointer, inserting at end requires traversing entire list each time, which is inefficient.

2. Step 2: Consider maintaining a tail pointer

   Adding a tail pointer updated on each insertion allows direct access to last node, making insertion O(1).

3. Final Answer:

   Create a tail pointer and update it during every insertion to avoid traversal -> Option C

4. Quick Check:

   Tail pointer avoids full traversal for tail insert [OK]

Hint: Keep tail pointer to insert at end efficiently [OK]

Common Mistakes:

• Ignoring tail pointer for efficiency
• Trying to swap data instead of pointers
• Reversing list unnecessarily