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.

Practice

1. Which of the following is a key advantage of using a linked list to implement a stack compared to using an array?

easy

A. Accessing elements by index is faster

B. It uses less pointer overhead

C. Memory usage is always less

D. The stack can grow dynamically without a fixed size limit

Solution

1. Step 1: Understand stack growth in arrays

   Arrays have a fixed size or require resizing, which can be costly.

2. Step 2: Understand linked list flexibility

   Linked lists allocate nodes dynamically, so the stack can grow as needed without a fixed limit.

3. Final Answer:

   The stack can grow dynamically without a fixed size limit -> Option D

4. Quick Check:

   Dynamic size = B [OK]

Hint: Linked list stacks grow dynamically; arrays have fixed size [OK]

Common Mistakes:

• Thinking arrays always use less memory
• Confusing access speed advantages
• Ignoring pointer overhead in linked lists

2. Which of the following is the correct way to push an element onto a stack implemented using a linked list in Python?

easy

A. Create a new node, set its next to current top, update top to new node

B. Append the element to the end of the linked list

C. Remove the last node and add the new element at the start

D. Replace the top node's value with the new element

Solution

1. Step 1: Recall push operation in linked list stack

   Push adds a new node at the start (top) of the list.

2. Step 2: Understand node linking

   The new node's next points to the current top, then top updates to new node.

3. Final Answer:

   Create a new node, set its next to current top, update top to new node -> Option A

4. Quick Check:

   Push = new node at top [OK]

Hint: Push means add new node at top, link to old top [OK]

Common Mistakes:

• Appending at end instead of start
• Replacing value instead of adding node
• Removing nodes during push

3. Consider this Python code using an array-based stack:

stack = []
stack.append(10)
stack.append(20)
stack.pop()
stack.append(30)
print(stack)

What is the output?

medium

A. [10, 30]

B. [20, 30]

C. [10, 20, 30]

D. [30]

Solution

1. Step 1: Trace stack operations step-by-step

   Start empty: [] append 10 -> [10] append 20 -> [10, 20] pop() removes 20 -> [10] append 30 -> [10, 30]

2. Step 2: Print final stack

   Final stack is [10, 30].

3. Final Answer:

   [10, 30] -> Option A

4. Quick Check:

   Stack after pop and append = [10, 30] [OK]

Hint: Pop removes last; append adds at end [OK]

Common Mistakes:

• Forgetting pop removes last element
• Assuming append adds at start
• Confusing stack order

4. The following code tries to implement a pop operation on a linked list stack but causes an error:

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

stack = Stack()
stack.pop()

What is the likely cause of the error?

medium

A. pop method returns wrong value

B. pop method does not update top pointer

C. Stack class is not defined or missing __init__ method

D. No error; code works fine

Solution

1. Step 1: Analyze code snippet

   pop method looks correct logically, but Stack class is not shown or initialized.

2. Step 2: Identify error cause

   Calling stack = Stack() without defining Stack class or __init__ causes NameError or AttributeError.

3. Final Answer:

   Stack class is not defined or missing __init__ method -> Option C

4. Quick Check:

   Undefined class = A [OK]

Hint: Check if class and constructor exist before method calls [OK]

Common Mistakes:

• Assuming pop method logic is wrong
• Ignoring missing class definition
• Thinking pop doesn't update top

5. You want to implement a stack for a program that requires frequent push and pop operations but has very limited memory. Which implementation is better and why? Array stack with fixed size or linked list stack?

hard

A. Linked list stack, because it is simpler to implement

B. Array stack, because it uses contiguous memory and less overhead

C. Array stack, because it allows faster random access

D. Linked list stack, because it uses dynamic memory and no wasted space

Solution

1. Step 1: Consider memory overhead

   Linked list nodes store extra pointers, increasing memory per element.

2. Step 2: Compare array memory usage

   Array stack uses contiguous memory without pointer overhead, so less memory per element if size is fixed.

3. Step 3: Evaluate suitability for limited memory

   Fixed size array stack is better when memory is limited and size is known.

4. Final Answer:

   Array stack, because it uses contiguous memory and less overhead -> Option B

5. Quick Check:

   Less overhead = Array stack = D [OK]

Hint: Fixed size + limited memory = array stack better [OK]

Common Mistakes:

• Assuming linked list always uses less memory
• Ignoring pointer overhead in linked lists
• Confusing dynamic size with memory efficiency