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.

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