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.