Stack Using Linked List vs Array Stack Trade-offs in DSA Python - Complexity Comparison

Time Complexity: Stack Using Linked List vs Array Stack Trade-offs

O(1)

Understanding Time Complexity

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

Which method handles push and pop operations more efficiently as the stack grows?

Scenario Under Consideration

Analyze the time complexity of push and pop operations in these two stack implementations.

class ArrayStack:
    def __init__(self):
        self.stack = []

    def push(self, val):
        self.stack.append(val)  # Add to end

    def pop(self):
        return self.stack.pop()  # Remove from end

class LinkedListNode:
    def __init__(self, val):
        self.val = val
        self.next = None

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

    def push(self, val):
        new_node = LinkedListNode(val)
        new_node.next = self.head
        self.head = new_node

    def pop(self):
        if not self.head:
            return None
        val = self.head.val
        self.head = self.head.next
        return val

These classes show stack operations using an array and a linked list.

Identify Repeating Operations

Both push and pop do a single main action each time they run.

• Primary operation: Adding or removing one element at the end (array) or head (linked list).
• How many times: Once per push or pop call, no loops involved.

How Execution Grows With Input

Each push or pop takes about the same time no matter how many items are in the stack.

Input Size (n)	Approx. Operations per push/pop
10	1
100	1
1000	1

Pattern observation: The time stays constant as the stack grows because push and pop only touch one element.

Final Time Complexity

Time Complexity: O(1)

This means push and pop operations take the same short time no matter how big the stack is.

Common Mistake

[X] Wrong: "Array stack push is slow because arrays need to resize often, so it's always slow."

[OK] Correct: Resizing happens only sometimes, so on average push is still very fast (amortized constant time).

Interview Connect

Knowing these trade-offs helps you explain why one stack type might be better in certain situations, showing your understanding of data structure choices.

Self-Check

"What if we used a dynamic array that doubles size when full for the array stack? How would that affect the time complexity of push?"