Stack Using Linked List vs Array Stack Trade-offs in DSA Python - Trade-offs & Analysis

Mental Model

A stack is a collection where you add and remove items from the top only. You can build it using a linked list or an array, each with its own strengths and weaknesses.

Analogy: Think of a stack like a stack of plates. Using an array is like having a fixed-size tray where plates are stacked, while a linked list is like stacking plates one by one without a fixed tray size.

Array Stack:
[0] -> Plate1
[1] -> Plate2
[2] -> Plate3
Top ↑ at index 2

Linked List Stack:
Plate3 -> Plate2 -> Plate1 -> null
Top ↑ at Plate3

Dry Run Walkthrough

Input: Push 3 plates in order: 1, 2, 3; then pop one plate

Goal: Show how pushing and popping works differently in array and linked list stacks and highlight trade-offs

Step 1: Push plate 1 onto array stack

Array: [1] -> null, Top ↑ at index 0
Linked List: null

Why: Start with empty stacks, add first plate to array at index 0

Step 2: Push plate 1 onto linked list stack

Array: [1] -> null, Top ↑ at index 0
Linked List: 1 -> null, Top ↑ at 1

Why: Add first plate as new node pointing to null

Step 3: Push plate 2 onto array stack

Array: [1] -> [2] -> null, Top ↑ at index 1
Linked List: 1 -> null, Top ↑ at 1

Why: Add plate 2 at next free index in array

Step 4: Push plate 2 onto linked list stack

Array: [1] -> [2] -> null, Top ↑ at index 1
Linked List: 2 -> 1 -> null, Top ↑ at 2

Why: Create new node for plate 2 pointing to previous top

Step 5: Push plate 3 onto array stack

Array: [1] -> [2] -> [3] -> null, Top ↑ at index 2
Linked List: 2 -> 1 -> null, Top ↑ at 2

Why: Add plate 3 at next free index in array

Step 6: Push plate 3 onto linked list stack

Array: [1] -> [2] -> [3] -> null, Top ↑ at index 2
Linked List: 3 -> 2 -> 1 -> null, Top ↑ at 3

Why: Create new node for plate 3 pointing to previous top

Step 7: Pop one plate from array stack

Array: [1] -> [2] -> null, Top ↑ at index 1
Linked List: 3 -> 2 -> 1 -> null, Top ↑ at 3

Why: Remove plate 3 by moving top index down

Step 8: Pop one plate from linked list stack

Array: [1] -> [2] -> null, Top ↑ at index 1
Linked List: 2 -> 1 -> null, Top ↑ at 2

Why: Remove plate 3 by moving top pointer to next node

Result:

Array Stack final: [1] -> [2] -> null, Top ↑ at index 1
Linked List Stack final: 2 -> 1 -> null, Top ↑ at 2

Annotated Code

DSA Python

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

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

    def push(self, value):
        new_node = Node(value)  # create new node
        new_node.next = self.top  # link new node to current top
        self.top = new_node  # update top to new node

    def pop(self):
        if self.top is None:
            return None  # empty stack
        popped_value = self.top.value
        self.top = self.top.next  # move top down
        return popped_value

    def __str__(self):
        curr = self.top
        values = []
        while curr:
            values.append(str(curr.value))
            curr = curr.next
        return ' -> '.join(values) + ' -> null'

class ArrayStack:
    def __init__(self, capacity=10):
        self.array = [None] * capacity
        self.top = -1
        self.capacity = capacity

    def push(self, value):
        if self.top + 1 == self.capacity:
            raise Exception('Stack Overflow')  # fixed size
        self.top += 1  # move top up
        self.array[self.top] = value  # place value

    def pop(self):
        if self.top == -1:
            return None  # empty stack
        popped_value = self.array[self.top]
        self.array[self.top] = None  # clear value
        self.top -= 1  # move top down
        return popped_value

    def __str__(self):
        if self.top == -1:
            return 'null'
        return ' -> '.join(str(self.array[i]) for i in range(self.top + 1)) + ' -> null'

# Driver code
linked_stack = LinkedListStack()
array_stack = ArrayStack(capacity=5)

# Push 1, 2, 3
for val in [1, 2, 3]:
    linked_stack.push(val)
    array_stack.push(val)

print('Linked List Stack after pushes:')
print(linked_stack)
print('Array Stack after pushes:')
print(array_stack)

# Pop one element
linked_pop = linked_stack.pop()
array_pop = array_stack.pop()

print(f'Popped from Linked List Stack: {linked_pop}')
print(f'Popped from Array Stack: {array_pop}')

print('Linked List Stack after pop:')
print(linked_stack)
print('Array Stack after pop:')
print(array_stack)

new_node.next = self.top # link new node to current top

link new node to previous top to maintain stack order

self.top = new_node # update top to new node

update top pointer to new node for push

self.top += 1 # move top up

increment top index to add new element in array

self.array[self.top] = value # place value

store new value at top index in array

self.top = self.top.next # move top down

pop by moving top pointer to next node

self.top -= 1 # move top down

pop by decrementing top index in array

Output

Linked List Stack after pushes:

3 -> 2 -> 1 -> null

Array Stack after pushes:

1 -> 2 -> 3 -> null

Popped from Linked List Stack: 3

Popped from Array Stack: 3

Linked List Stack after pop:

2 -> 1 -> null

Array Stack after pop:

1 -> 2 -> null

Complexity Analysis

Time: O(1) for push and pop because both linked list and array stacks add or remove from the top directly

Space: O(n) for both, but linked list uses extra space per node for pointers while array uses fixed contiguous space

vs Alternative: Linked list stack grows dynamically without fixed size but uses extra memory; array stack is faster in memory but limited by fixed capacity and resizing cost

Edge Cases

Pop from empty stack

Returns None without error

DSA Python

if self.top is None: return None  # empty stack (linked list)

Push beyond array capacity

Raises 'Stack Overflow' exception

DSA Python

if self.top + 1 == self.capacity: raise Exception('Stack Overflow')

Single element stack push and pop

Works normally, top updates correctly

DSA Python

self.top = new_node (linked list) and self.top += 1 (array)

When to Use This Pattern

When a problem needs last-in-first-out order with dynamic size or fixed size constraints, consider stack implementations and choose linked list for dynamic size or array for faster access and fixed size.

Common Mistakes

Mistake: Forgetting to update the top pointer after push or pop in linked list stack
Fix: Always assign self.top to new_node on push and to self.top.next on pop

Mistake: Not checking for stack overflow in array stack push
Fix: Add capacity check before incrementing top index

Summary

Stack can be built using linked list or array with push/pop at the top.

Use linked list stack when size can change dynamically; use array stack for fixed size and faster memory access.

Linked list stack uses pointers to grow dynamically; array stack uses contiguous memory with fixed capacity.