Insert at End Tail Insert in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Tail Insert in a Singly Linked List

What is the printed state of the linked list after inserting 10, 20, and 30 at the end using tail insertion?

DSA C++

#include <iostream>

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;
            return;
        }
        Node* temp = head;
        while (temp->next) {
            temp = temp->next;
        }
        temp->next = newNode;
    }

    void printList() {
        Node* temp = head;
        while (temp) {
            std::cout << temp->data << " -> ";
            temp = temp->next;
        }
        std::cout << "null" << std::endl;
    }
};

int main() {
    LinkedList list;
    list.insertAtEnd(10);
    list.insertAtEnd(20);
    list.insertAtEnd(30);
    list.printList();
    return 0;
}

A null

B 10 -> 20 -> 30 -> null

C 10 -> 30 -> 20 -> null

D 30 -> 20 -> 10 -> null

💡 Hint

Think about how tail insertion adds nodes at the end, preserving order.

Tail insertion adds each new node at the end of the list, so the order of insertion is preserved in the list.

❓ Predict Output

intermediate

Resulting List After Multiple Tail Inserts

What is the linked list state after inserting 5, then 15, then 25 at the end?

DSA C++

#include <iostream>

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;
            return;
        }
        Node* temp = head;
        while (temp->next) {
            temp = temp->next;
        }
        temp->next = newNode;
    }

    void printList() {
        Node* temp = head;
        while (temp) {
            std::cout << temp->data << " -> ";
            temp = temp->next;
        }
        std::cout << "null" << std::endl;
    }
};

int main() {
    LinkedList list;
    list.insertAtEnd(5);
    list.insertAtEnd(15);
    list.insertAtEnd(25);
    list.printList();
    return 0;
}

A 25 -> 15 -> 5 -> null

B null

C 5 -> 25 -> 15 -> null

D 5 -> 15 -> 25 -> null

💡 Hint

Tail insertion keeps the order of insertion intact.

Each new node is added at the end, so the list order matches insertion order.

🔧 Debug

advanced

Identify the Bug in Tail Insert Function

What error will occur when running this tail insert code snippet?

DSA C++

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 == nullptr) {
            head = newNode;
            return;
        }
        Node* temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
};

A Runtime error: infinite loop or segmentation fault

B No error, works correctly

C Compilation error: missing return type

D Logical error: inserts at beginning instead of end

💡 Hint

Check what happens when the list is empty and you assign head = newNode but continue to use temp.

When head is nullptr, head is set to newNode but the code continues to traverse from head, which now points to newNode. Then temp->next is assigned newNode again, creating a cycle causing infinite loop or crash.

❓ Predict Output

advanced

Output After Tail Insert with Multiple Nodes

What is the output after inserting nodes with values 1, 2, 3, 4, 5 at the end of an empty list?

DSA C++

#include <iostream>

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;
            return;
        }
        Node* temp = head;
        while (temp->next) {
            temp = temp->next;
        }
        temp->next = newNode;
    }

    void printList() {
        Node* temp = head;
        while (temp) {
            std::cout << temp->data << " -> ";
            temp = temp->next;
        }
        std::cout << "null" << std::endl;
    }
};

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

A 1 -> 2 -> 3 -> 4 -> 5 -> null

B 5 -> 4 -> 3 -> 2 -> 1 -> null

C 1 -> 3 -> 5 -> 2 -> 4 -> null

D null

💡 Hint

Tail insertion preserves the order of insertion.

Nodes are added at the end, so the list shows values in the order inserted.

🧠 Conceptual

expert

Time Complexity of Tail Insert in Singly Linked List Without Tail Pointer

What is the time complexity of inserting a node at the end of a singly linked list when you do NOT maintain a tail pointer?

A O(log n) logarithmic time

B O(1) constant time

C O(n) linear time

D O(n^2) quadratic time

💡 Hint

Think about how many nodes you must visit to find the end each time.

Without a tail pointer, you must traverse the entire list to find the last node before inserting, which takes linear time proportional to the list size.

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