Stack Implementation Using Linked List in DSA Python - Execution Trace

Concept Flow - Stack Implementation Using Linked List

Create new node with data

↓

Set new node.next to current top

↓

Update top pointer to new node

↓

Stack push complete

↓

Check if top is None?

Yes↓

Stack is empty

No↓

Access top node data

↓

Update top to top.next

↓

Stack pop complete

Push adds a new node at the top by linking it to the current top. Pop removes the top node by moving the top pointer to the next node.

Execution Sample

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

stack = Stack()
stack.push(10)
stack.push(20)
popped_value = stack.pop()

This code creates a stack using linked list nodes, pushes 10 and 20, then pops the top value.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Initialize stack	None	top = None	top -> None
2	Push 10	Node(10)	new_node.next = None, top = new_node	top -> [10] -> None
3	Push 20	Node(20) -> Node(10)	new_node.next = top(10), top = new_node(20)	top -> [20] -> [10] -> None
4	Pop top	Node(10)	top moves from 20 to 10	top -> [10] -> None
5	Pop returns	Node(10)	top = Node(10)	top -> [10] -> None
6	End	Node(10)	No change	top -> [10] -> None

💡 Pop stops because top is updated to next node; stack is not empty after pop.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
top	None	Node(10)	Node(20)	Node(10)	Node(10)
new_node	N/A	Node(10)	Node(20)	N/A	N/A
popped	N/A	N/A	N/A	20	20

Key Moments - 3 Insights

Why does push set new_node.next to top before updating top?

Because the new node must point to the current top to keep the stack linked. See Step 3 in execution_table where new_node.next = top(10) before top updates to new_node(20).

What happens if pop is called when stack is empty?

Pop returns None immediately because top is None. This is shown in Step 1 where top is None, so pop would detect empty stack and stop.

Why does pop update top to top.next?

Because removing the top means the next node becomes the new top. Step 4 shows top moving from Node(20) to Node(10), effectively removing the old top.

Visual Quiz - 3 Questions

Look at the execution_table, what is the visual state after pushing 20?

A top -> [20] -> [10] -> None

B top -> [10] -> None

C top -> [20] -> None

D top -> None

💡 Hint

Check Step 3 in execution_table under Visual State.

At which step does the top pointer move from Node(20) to Node(10)?

A Step 2

B Step 4

C Step 3

D Step 5

💡 Hint

Look at Pointer Changes column in execution_table.

If we pop again after Step 4, what will be the new top?

A Node(20)

B Node(10)

C None

D Node(30)

💡 Hint

After popping Node(10), top moves to None because stack becomes empty.

Concept Snapshot

Stack using linked list:
- Push: create node, point new_node.next to top, update top
- Pop: return top.data, update top to top.next
- top points to stack's top node
- Empty stack when top is None
- LIFO order maintained by linked nodes

Full Transcript

This visualization shows how a stack is built using a linked list. We start with an empty stack where top is None. When pushing, a new node is created and linked to the current top, then top is updated to this new node. When popping, the top node's data is returned and top moves to the next node. The execution table tracks each step, showing nodes in the list, pointer changes, and the visual state of the stack. Key moments clarify why pointers are updated in a certain order and what happens when popping from an empty stack. The quiz tests understanding of the stack's state after operations. This method keeps the stack in LIFO order using linked nodes.