Insert at End Tail Insert in DSA C - Time & Space Complexity

Time Complexity: Insert at End Tail Insert

O(n)

Understanding Time Complexity

We want to understand how the time to add a new item at the end of a linked list changes as the list grows.

How does the number of steps grow when we insert at the tail?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Insert a new node at the end of a singly linked list
void insertAtEnd(Node** head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;

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

    Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}
    

This code creates a new node and adds it to the end of a singly linked list by traversing from the head.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that moves through each node until the last one.
• How many times: It runs once for each node in the list until the end, so n times if the list has n nodes.

How Execution Grows With Input

As the list gets longer, the time to find the end grows linearly because we check each node one by one.

Input Size (n)	Approx. Operations
10	About 10 steps to reach the end
100	About 100 steps to reach the end
1000	About 1000 steps to reach the end

Pattern observation: The steps increase directly with the number of nodes, so doubling nodes doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to insert at the end grows in direct proportion to the list size.

Common Mistake

[X] Wrong: "Inserting at the end is always fast and takes constant time."

[OK] Correct: Without a pointer to the last node, we must walk through the whole list, so time grows with list length.

Interview Connect

Understanding this helps you explain why adding at the tail can be slow without extra pointers, showing you know how data structure design affects speed.

Self-Check

"What if we kept a pointer to the last node (tail) in the list? How would the time complexity change?"