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

Time Complexity: Insert at End Tail Insert

O(n)

Understanding Time Complexity

We want to understand how long it takes to add a new item at the end of a list or linked list.

How does the time needed grow as the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def insert_at_end(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

This code adds a new node at the end of a linked list by walking through all nodes until it finds the last one.

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 already in the list, so n times if there are n nodes.

How Execution Grows With Input

As the list grows, the time to find the end grows too, 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 grow directly with the number of nodes, so doubling nodes doubles the steps.

Final Time Complexity

Time Complexity: O(n)

This means the time to insert at the end grows linearly with 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 all nodes, so time grows with list size.

Interview Connect

Knowing how insertion time changes with list size helps you explain trade-offs in data structures clearly and confidently.

Self-Check

"What if we kept a pointer to the last node? How would the time complexity change?"