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

Challenge - 5 Problems

🧠 Conceptual

intermediate

Memory Usage Comparison

Which statement correctly describes the memory usage difference between a stack implemented using a linked list and one using an array?

A Linked list stack uses extra memory for pointers, while array stack uses contiguous memory without extra pointers.

B Array stack uses extra memory for pointers, while linked list stack uses contiguous memory without extra pointers.

C Both linked list and array stacks use the same amount of memory per element.

D Linked list stack uses less memory overall because it stores only data without pointers.

💡 Hint

Think about how linked lists store each element compared to arrays.

A linked list stack stores each element in a node that contains data and a pointer to the next node, which uses extra memory. An array stack stores elements in contiguous memory without pointers.

❓ Predict Output

intermediate

Stack Overflow Behavior

What will be the output of the following Python code simulating a stack push operation on an array stack with fixed size 3?

DSA Python

class ArrayStack:
    def __init__(self):
        self.stack = [None]*3
        self.top = -1
    def push(self, val):
        if self.top == 2:
            print('Stack Overflow')
        else:
            self.top += 1
            self.stack[self.top] = val
            print(f'Pushed {val}')

s = ArrayStack()
s.push(10)
s.push(20)
s.push(30)
s.push(40)

A

Stack Overflow
Stack Overflow
Stack Overflow
Stack Overflow

B

Pushed 10
Pushed 20
Stack Overflow
Pushed 30

C

Pushed 10
Pushed 20
Pushed 30
Stack Overflow

D

Pushed 10
Pushed 20
Pushed 30
Pushed 40

💡 Hint

Check the condition that triggers overflow before pushing.

The stack size is fixed at 3. The first three pushes succeed. The fourth push detects top == 2 (last index) and prints 'Stack Overflow'.

❓ Predict Output

advanced

Linked List Stack Push and Pop

What is the printed output after executing this linked list stack code?

DSA Python

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

class LinkedListStack:
    def __init__(self):
        self.top = None
    def push(self, val):
        new_node = Node(val)
        new_node.next = self.top
        self.top = new_node
    def pop(self):
        if self.top is None:
            print('Stack Underflow')
            return
        print(f'Popped {self.top.val}')
        self.top = self.top.next

s = LinkedListStack()
s.push(5)
s.push(10)
s.pop()
s.pop()
s.pop()

A

Popped 10
Stack Underflow
Popped 5

B

Popped 10
Popped 5
Stack Underflow

C

Stack Underflow
Popped 10
Popped 5

D

Popped 5
Popped 10
Stack Underflow

💡 Hint

Remember that push adds to the top and pop removes from the top.

Push 5, then push 10 makes 10 the top. First pop removes 10, second pop removes 5, third pop finds stack empty and prints 'Stack Underflow'.

🧠 Conceptual

advanced

Time Complexity Trade-offs

Which statement correctly compares the time complexity of push and pop operations in array stack vs linked list stack implementations?

A Both array and linked list stacks have O(1) time complexity for push and pop in average cases.

B Linked list stack pop is O(n), array stack pop is O(1).

C Array stack push is O(n) due to resizing, linked list stack push is always O(1).

D Array stack push and pop are O(1), linked list stack push and pop are O(n).

💡 Hint

Consider typical implementations without resizing costs.

Both array and linked list stacks perform push and pop in constant time O(1) on average. Array resizing can cause occasional O(n), but average remains O(1).

🚀 Application

expert

Choosing Stack Implementation for Unknown Size

You need to implement a stack where the maximum number of elements is unknown and can grow very large. Which implementation is best and why?

A Linked list stack, because it uses less memory per element than array stack.

B Array stack with fixed size, because it uses less memory and is faster.

C Array stack with large fixed size, to avoid resizing during push operations.

D Linked list stack, because it can grow dynamically without resizing overhead.

💡 Hint

Think about memory allocation and resizing when size is unknown.

Linked list stacks grow dynamically without needing to resize or allocate large contiguous memory blocks, making them suitable for unknown or large sizes.

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