Stack Implementation Using Linked List in DSA Python

Mental Model

A stack is like a pile where you add and remove items only from the top. Using a linked list means each item points to the one below it.

Analogy: Imagine stacking plates: you put a new plate on top and take the top plate off first. Each plate holds the next plate underneath.

Top -> [Node1] -> [Node2] -> [Node3] -> null
↑ (top points here)

Dry Run Walkthrough

Input: Push 10, then push 20, then pop once

Goal: Show how the stack changes with push and pop using linked list nodes

Step 1: Push 10 onto empty stack

Top -> [10] -> null
↑

Why: First item becomes the top node

Step 2: Push 20 onto stack

Top -> [20] -> [10] -> null
↑

Why: New node points to previous top, becomes new top

Step 3: Pop top item (20)

Top -> [10] -> null
↑

Why: Remove top node, top moves to next node

Result:

Top -> [10] -> null
↑
Popped value: 20

Annotated Code

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, value):
        new_node = Node(value)
        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  # stack empty
        popped_value = self.top.data
        self.top = self.top.next  # move top down
        return popped_value

    def __str__(self):
        result = []
        current = self.top
        while current:
            result.append(str(current.data))
            current = current.next
        return ' -> '.join(result) + ' -> null'

# Driver code
stack = Stack()
stack.push(10)
stack.push(20)
popped = stack.pop()
print(stack)
print(f"Popped value: {popped}")

new_node.next = self.top # link new node to current top

connect new node to current top to keep stack order

self.top = new_node # update top to new node

move top pointer to new node after push

if self.top is None: return None # stack empty

check if stack is empty before pop

self.top = self.top.next # move top down

remove top node by moving top pointer down

Output

20 -> 10 -> null

Popped value: 20

Complexity Analysis

Time: O(1) for push and pop because we only change the top pointer without traversing

Space: O(n) because each pushed item creates a new node stored in memory

vs Alternative: Compared to array-based stack, linked list avoids resizing but uses extra memory for pointers

Edge Cases

Pop from empty stack

Returns None safely without error

DSA Python

if self.top is None:
    return None  # stack empty

Push single element

Stack top points to the new single node

DSA Python

new_node.next = self.top  # link new node to current top

When to Use This Pattern

When you need last-in-first-out order with dynamic size and want fast push/pop, use stack with linked list for efficient top operations.

Common Mistakes

Mistake: Forgetting to update the top pointer after push or pop
Fix: Always assign self.top to the new node after push and to next node after pop

Mistake: Not handling pop on empty stack causing errors
Fix: Check if top is None before popping and return None or handle gracefully

Summary

Implements a stack using linked nodes where each new item is added or removed from the top.

Use when you want a stack that grows dynamically without fixed size limits.

The key is to always update the top pointer to add or remove the top element efficiently.

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