Stack Implementation Using Linked List in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a stack data structure?

A stack is a collection where elements are added and removed in a last-in, first-out (LIFO) order. Think of a stack of plates where you add or remove the top plate only.

intermediate

What is the main advantage of using a linked list to implement a stack?

Using a linked list allows the stack to grow and shrink dynamically without a fixed size limit, unlike arrays which have a fixed size.

beginner

What does the 'push' operation do in a stack implemented with a linked list?

The 'push' operation adds a new element at the top of the stack by creating a new node and linking it as the new head of the list.

beginner

What happens during the 'pop' operation in a linked list stack?

The 'pop' operation removes the top element by unlinking the head node and returning its value, then updating the head to the next node.

beginner

Why is it important to check if the stack is empty before popping?

Because popping from an empty stack causes an error or undefined behavior. Checking prevents trying to remove from an empty list.

What order does a stack follow when adding and removing elements?

A Random Order

B First In, First Out (FIFO)

C Last In, First Out (LIFO)

D Sorted Order

A stack follows Last In, First Out (LIFO) order, meaning the last element added is the first one removed.

In a linked list stack, where is the new element added during a push?

A At the head (start) of the list

B At the tail (end) of the list

C In the middle of the list

D At a random position

New elements are added at the head of the linked list to represent the top of the stack.

What should you do before performing a pop operation on a stack?

A Clear the stack

B Check if the stack is empty

C Sort the stack

D Add a new element

Always check if the stack is empty to avoid errors when popping.

What is the time complexity of push and pop operations in a linked list stack?

A O(n^2)

B O(n)

C O(log n)

D O(1)

Both push and pop operations take constant time O(1) because they only involve the head node.

Which of the following is NOT a benefit of using a linked list for stack implementation?

A Faster random access

B Dynamic size

C No wasted space

D Easy insertion and deletion at head

Linked lists do not provide fast random access; accessing elements by index is slower compared to arrays.

Explain how push and pop operations work in a stack implemented using a linked list.

Think about adding and removing from the start of the linked list.

Describe the advantages of using a linked list over an array for implementing a stack.

Consider flexibility and memory usage differences.

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