Stack Implementation Using Linked List in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the top of the stack as empty.

DSA Python

class Stack:
    def __init__(self):
        self.top = [1]

Drag options to blanks, or click blank then click option'

A[]

BNode()

C0

DNone

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 or an empty list instead of None for top.

The top of an empty stack is set to None to indicate no nodes are present.

2fill in blank

medium

Complete the code to create a new node with the given data.

DSA Python

class Node:
    def __init__(self, data):
        self.data = data
        self.next = [1]

Drag options to blanks, or click blank then click option'

Aself

Bdata

CNone

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Setting next to data or 0 instead of None.

The next pointer of a new node is set to None because it does not point to any other node yet.

3fill in blank

hard

Fix the error in the push method to correctly add a new node on top of the stack.

DSA Python

def push(self, data):
    new_node = Node(data)
    new_node.next = [1]
    self.top = new_node

Drag options to blanks, or click blank then click option'

Aself.top.next

Bself.top

CNone

Dnew_node

Attempts:

3 left

💡 Hint

Common Mistakes

Linking new_node.next to None or new_node itself.

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

4fill in blank

hard

Fill both blanks to correctly remove the top node and update the stack.

DSA Python

def pop(self):
    if self.top is None:
        return None
    popped_node = self.top
    self.top = [1]
    popped_node.next = [2]
    return popped_node.data

Drag options to blanks, or click blank then click option'

Aself.top.next

BNone

Cself.top

Dpopped_node

Attempts:

3 left

💡 Hint

Common Mistakes

Setting top to popped_node or None incorrectly.

After popping, top moves to the next node, and popped_node.next is set to None to detach it.

5fill in blank

hard

Fill all three blanks to check if the stack is empty and return the top element's data.

DSA Python

def peek(self):
    if self.top == [1]:
        return [2]
    return self.top.[3]

Drag options to blanks, or click blank then click option'

ANone

Cdata

Dnext

Attempts:

3 left

💡 Hint

Common Mistakes

Returning top or next instead of data, or wrong empty check.

Peek returns None if stack is empty (top is None), else returns the data of the top node.

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