Push Using Linked List Node in DSA Python - Time & Space Complexity

Time Complexity: Push Using Linked List Node

O(1)

Understanding Time Complexity

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

How does the time needed change as the list grows?

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 push(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node

This code adds a new node at the beginning of the linked list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Creating a new node and updating pointers.
• How many times: This happens once per push call, no loops or recursion inside.

How Execution Grows With Input

Adding a node always takes the same steps, no matter how big the list is.

Input Size (n)	Approx. Operations
10	3 steps (create node, update pointers)
100	3 steps (same as above)
1000	3 steps (still the same)

Pattern observation: The time stays constant regardless of list size.

Final Time Complexity

Time Complexity: O(1)

This means adding a node at the start takes the same short time no matter how many nodes are already in the list.

Common Mistake

[X] Wrong: "Adding a node takes longer as the list grows because we have to move through the list."

[OK] Correct: We only change the first node's pointer, so we never walk through the list. The operation is always quick.

Interview Connect

Knowing this helps you explain why linked lists are good for quick insertions at the start, a useful skill in many coding problems.

Self-Check

"What if we changed push to add a node at the end of the linked list? How would the time complexity change?"