Stack Implementation Using Linked List in DSA Python - Time & Space Complexity

Time Complexity: Stack Implementation Using Linked List

O(1)

Understanding Time Complexity

We want to understand how fast stack operations run when using a linked list.

How does the time to push or pop change as the stack grows?

Scenario Under Consideration

Analyze the time complexity of the following stack operations using a linked list.

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

class Stack:
    def __init__(self):
        self.top = None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.top
        self.top = new_node

    def pop(self):
        if self.top is None:
            return None
        popped = self.top.data
        self.top = self.top.next
        return popped

This code adds (push) and removes (pop) items at the top of the stack using linked nodes.

Identify Repeating Operations

Look for loops or repeated steps in push and pop.

• Primary operation: Assigning pointers to add or remove the top node.
• How many times: Each push or pop does a fixed number of steps, no loops.

How Execution Grows With Input

Each push or pop takes the same small number of steps no matter how big the stack is.

Input Size (n)	Approx. Operations
10	5-6 steps per push/pop
100	5-6 steps per push/pop
1000	5-6 steps per push/pop

Pattern observation: The time stays about the same no matter how many items are in the stack.

Final Time Complexity

Time Complexity: O(1)

This means each push or pop happens in constant time, quickly and independently of stack size.

Common Mistake

[X] Wrong: "Push or pop takes longer as the stack grows because there are more nodes."

[OK] Correct: Push and pop only change the top node pointer, so they do not look through the whole stack.

Interview Connect

Knowing that stack operations with linked lists run in constant time shows you understand efficient data handling, a key skill in coding interviews.

Self-Check

"What if we changed the stack to use an array instead of a linked list? How would the time complexity of push and pop change?"