Insert at End Tail Insert in DSA C++

Mental Model

Add a new item at the very end of a chain of items by moving to the last one and linking the new item after it.

Analogy: Imagine a line of people holding hands. To add a new person at the end, you walk to the last person and hold their hand.

head -> 1 -> 2 -> 3 -> null
                 ↑

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3, insert value 4 at end

Goal: Add the value 4 as the last item in the list

Step 1: start at head node (value 1)

head -> [1] -> 2 -> 3 -> null

Why: We begin at the start to find the end

Step 2: move to next node (value 2)

head -> 1 -> [2] -> 3 -> null

Why: Keep moving forward to reach the last node

Step 3: move to next node (value 3)

head -> 1 -> 2 -> [3] -> null

Why: We found the last node because its next is null

Step 4: link new node with value 4 after last node

head -> 1 -> 2 -> 3 -> [4] -> null

Why: Attach the new node at the end to complete insertion

Result:

head -> 1 -> 2 -> 3 -> 4 -> null

Annotated Code

DSA C++

#include <iostream>
using namespace std;

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

class LinkedList {
public:
    Node* head;
    LinkedList() : head(nullptr) {}

    void insertAtEnd(int val) {
        Node* newNode = new Node(val);
        if (!head) {
            head = newNode; // empty list, new node is head
            return;
        }
        Node* curr = head;
        while (curr->next != nullptr) {
            curr = curr->next; // advance curr to next node
        }
        curr->next = newNode; // link new node at end
    }

    void printList() {
        Node* curr = head;
        while (curr != nullptr) {
            cout << curr->data;
            if (curr->next) cout << " -> ";
            curr = curr->next;
        }
        cout << " -> null" << endl;
    }
};

int main() {
    LinkedList list;
    list.insertAtEnd(1);
    list.insertAtEnd(2);
    list.insertAtEnd(3);
    list.insertAtEnd(4);
    list.printList();
    return 0;
}

if (!head) { head = newNode; // empty list, new node is head return; }

handle empty list by making new node the head

while (curr->next != nullptr) { curr = curr->next; // advance curr to next node }

advance curr to last node where next is null

curr->next = newNode; // link new node at end

attach new node after last node

Output

1 -> 2 -> 3 -> 4 -> null

Complexity Analysis

Time: O(n) because we traverse all nodes once to reach the end

Space: O(1) because we only use a few pointers regardless of list size

vs Alternative: Compared to inserting at the front (O(1)), tail insert takes longer because we must find the last node

Edge Cases

empty list

new node becomes the head directly

DSA C++

if (!head) {
    head = newNode; // empty list, new node is head
    return;
}

single element list

new node is linked after the single existing node

DSA C++

while (curr->next != nullptr) {
    curr = curr->next; // advance curr to next node
}

When to Use This Pattern

When you need to add an item at the end of a linked list, use tail insertion by traversing to the last node and linking the new node after it.

Common Mistakes

Mistake: Not handling empty list case, causing null pointer errors
Fix: Check if head is null before traversal and assign new node as head if so

Mistake: Linking new node before reaching the last node
Fix: Traverse until curr->next is null before linking new node

Summary

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

Use when you want to keep the existing order and append new data at the tail.

The key is to find the last node whose next pointer is null and link the new node there.

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