Stack Implementation Using Linked List in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output after these stack operations?

Consider a stack implemented using a linked list. The following operations are performed in order:

1. push(10)
2. push(20)
3. pop()
4. push(30)
5. pop()
6. push(40)

What is the printed state of the stack from top to bottom?

DSA Python

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

    def print_stack(self):
        current = self.top
        result = []
        while current:
            result.append(str(current.data))
            current = current.next
        print(" -> ".join(result) + " -> null")

stack = Stack()
stack.push(10)
stack.push(20)
stack.pop()
stack.push(30)
stack.pop()
stack.push(40)
stack.print_stack()

A 40 -> 10 -> null

B 20 -> 10 -> null

C 30 -> 10 -> null

D 10 -> 40 -> null

💡 Hint

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

After the operations, the stack top is 40, then 10 below it, then null.

❓ Predict Output

intermediate

What error occurs when popping from an empty stack?

Given the stack implementation below, what happens if we call pop() on an empty stack?

DSA Python

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

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

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

stack = Stack()
print(stack.pop())

A TypeError

B None

C AttributeError

D IndexError

💡 Hint

Check the condition when the stack is empty before popping.

The pop method returns None if the stack is empty, so no error occurs.

🔧 Debug

advanced

Identify the bug in this push method

Look at the push method below. What is the bug that will cause incorrect stack behavior?

DSA Python

def push(self, data):
    new_node = Node(data)
    if self.top is None:
        self.top = new_node
    else:
        self.top.next = new_node
        self.top = new_node

A The new node is added at the bottom instead of the top

B The top pointer is not updated correctly

C The next pointer of the new node is not set to the current top

D The method does not create a new node

💡 Hint

Remember the linked list stack adds new nodes at the front.

The new node's next pointer must point to the current top node before updating top.

🚀 Application

advanced

How many elements remain after these operations?

Starting with an empty stack, perform these operations:

1. push(5)
2. push(15)
3. pop()
4. push(25)
5. push(35)
6. pop()
7. pop()

How many elements remain in the stack?

DSA Python

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

    def size(self):
        count = 0
        current = self.top
        while current:
            count += 1
            current = current.next
        return count

stack = Stack()
stack.push(5)
stack.push(15)
stack.pop()
stack.push(25)
stack.push(35)
stack.pop()
stack.pop()
print(stack.size())

A 0

B 2

C 3

D 1

💡 Hint

Count pushes and pops carefully.

After all operations, only one element remains in the stack.

🧠 Conceptual

expert

Why is linked list preferred over array for stack in some cases?

Which reason best explains why a linked list implementation of a stack might be preferred over an array implementation?

A Linked list allows dynamic size without resizing overhead

B Linked list uses less memory than arrays always

C Linked list provides faster access to middle elements

D Linked list requires less code to implement than arrays

💡 Hint

Think about how arrays handle size changes.

Linked lists grow dynamically without needing to resize, unlike arrays which may need costly resizing.

Practice

1. What is the main advantage of implementing a stack using a linked list instead of an array?

easy

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

B. It uses less memory than an array

C. It allows random access to elements

D. It is easier to sort the stack elements

Solution

1. Step 1: Understand stack size limitation in arrays

   Arrays have a fixed size, so stacks implemented with arrays have a maximum capacity.

2. Step 2: Linked list dynamic size advantage

   Linked lists allocate memory dynamically, so the stack can grow as needed without size limits.

3. Final Answer:

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

4. Quick Check:

   Linked list stacks grow dynamically [OK]

Hint: Linked list stacks grow dynamically, arrays do not [OK]

Common Mistakes:

• Thinking linked lists use less memory always
• Confusing stack with queue behavior
• Assuming random access is possible in stacks

2. Which of the following is the correct way to create a new node class for a linked list stack in Python?

easy

A. class Node:\n def __init__(self):\n self.data = None\n self.next = None

B. class Node:\n def __init__(self, data, next):\n self.data = data\n self.next = next

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

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

Solution

1. Step 1: Check Node class constructor parameters

   The node should store data and a pointer to next node, initialized to None.

2. Step 2: Verify correct attribute assignment

   class Node:\n def __init__(self, data):\n self.data = data\n self.next = None correctly assigns data and sets next to None for a new node.

3. Final Answer:

   class Node:\n def __init__(self, data):\n self.data = data\n self.next = None -> Option C

4. Quick Check:

   Node stores data and next pointer [OK]

Hint: Node needs data and next pointer initialized to None [OK]

Common Mistakes:

• Swapping data and next assignments
• Forgetting to initialize next to None
• Adding unnecessary parameters in constructor

3. What will be the output of the following code snippet implementing push and print operations on a linked list stack?

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 print_stack(self):
        current = self.top
        while current:
            print(current.data, end=' -> ')
            current = current.next
        print('null')

stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)
stack.print_stack()

medium

A. 30 -> 20 -> 10 -> null

B. 10 -> 20 -> 30 -> null

C. null -> 10 -> 20 -> 30

D. 30 -> null -> 20 -> 10

Solution

1. Step 1: Trace push operations

   Push 10: top points to node with 10. Push 20: new node with 20 points to 10, top updated to 20. Push 30: new node with 30 points to 20, top updated to 30.

2. Step 2: Trace print_stack output

   Print starts at top (30), then 20, then 10, then null.

3. Final Answer:

   30 -> 20 -> 10 -> null -> Option A

4. Quick Check:

   Stack top is last pushed [OK]

Hint: Stack prints from top to bottom, last pushed first [OK]

Common Mistakes:

• Printing in insertion order instead of stack order
• Confusing next pointer direction
• Forgetting to print null at end

4. Identify the error in the following pop method of a linked list stack and select the correct fix:

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

medium

A. Raise exception instead of returning null when stack is empty

B. Check if popped_node.next is null before assigning

C. Set popped_node.next to null before returning

D. Return popped_node.data instead of popped_node

Solution

1. Step 1: Understand pop method return value

   Pop should return the data of the popped node, not the node object itself.

2. Step 2: Fix return statement

   Change return popped_node to return popped_node.data to return the value.

3. Final Answer:

   Return popped_node.data instead of popped_node -> Option D

4. Quick Check:

   Pop returns data, not node object [OK]

Hint: Pop returns data, not node object [OK]

Common Mistakes:

• Returning node object instead of data
• Not updating top pointer
• Not handling empty stack case

5. You want to implement a function reverse_stack that reverses the elements of a stack implemented using a linked list without using extra data structures. Which approach correctly achieves this?

hard

A. Traverse the linked list and swap data of nodes pairwise from start to end

B. Recursively pop all elements, then push them back in reverse order

C. Use a temporary array to store elements, then push back in reverse

D. Create a new stack and push elements from the original stack to it

Solution

1. Step 1: Understand constraints - no extra data structures

   Options C and D use extra structures (array or new stack), so they are invalid.

2. Step 2: Recursive approach to reverse stack

   Recursively pop elements until empty, then push them back in reverse order using call stack, reversing the stack without extra storage.

3. Final Answer:

   Recursively pop all elements, then push them back in reverse order -> Option B

4. Quick Check:

   Recursion reverses stack without extra data structures [OK]

Hint: Use recursion to reverse stack without extra storage [OK]

Common Mistakes:

• Using extra arrays or stacks despite constraints
• Trying to swap node data incorrectly
• Not handling base case in recursion