Stack Implementation Using Linked List in DSA Rust - Execution Trace

Concept Flow - Stack Implementation Using Linked List

Start

↓

Create new node with data

↓

Set new node.next to current head

↓

Update head to new node

↓

Stack push complete

↓

For pop: Check if head is None?

↓

Save head data

↓

Update head to head.next

↓

Return saved data

↓

Stack pop complete

Push adds a new node at the start (head) of the linked list. Pop removes the head node and returns its data.

Execution Sample

DSA Rust

struct Node {
    data: i32,
    next: Option<Box<Node>>,
}

// Push: new node points to head, head updated
// Pop: remove head, head moves to next

This code shows how to add (push) and remove (pop) elements from a stack using a linked list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Push 10	10	head -> new node(10)	10 -> null
2	Push 20	20 -> 10	new node(20).next = head(10), head -> 20	20 -> 10 -> null
3	Push 30	30 -> 20 -> 10	new node(30).next = head(20), head -> 30	30 -> 20 -> 10 -> null
4	Pop	20 -> 10	head moves from 30 to 20	20 -> 10 -> null
5	Pop	10	head moves from 20 to 10	10 -> null
6	Pop	empty	head moves from 10 to null	null
7	Pop	empty	head is null, cannot pop	null

💡 Execution stops after pop on empty stack because head is None (stack empty).

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7
head	null	Node(10)	Node(20)	Node(30)	Node(20)	Node(10)	null	null
stack size	0	1	2	3	2	1	0	0

Key Moments - 3 Insights

Why does push add the new node at the head instead of the tail?

Because adding at the head is fast and simple: just point new node.next to current head and update head. See execution_table steps 1-3 where new nodes become the new head.

What happens if we pop when the stack is empty?

Pop checks if head is None. If yes, it cannot remove any node. See execution_table step 7 where pop fails because head is null.

Why does pop update head to head.next?

Because the top of the stack is the head node. Removing it means head moves to the next node. See execution_table steps 4-6 where head moves forward.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the visual state of the stack?

A 30 -> 20 -> 10 -> null

B 10 -> 20 -> 30 -> null

C 20 -> 30 -> 10 -> null

D null

💡 Hint

Check the Visual State column at step 3 in execution_table.

At which step does the stack become empty?

A Step 5

B Step 6

C Step 7

D Step 4

💡 Hint

Look at the Nodes in List and Visual State columns to see when head becomes null.

If we push 40 after step 3, what will be the new head node data?

A 10

B 20

C 30

D 40

💡 Hint

Push adds new node at head, so new head data is the pushed value.

Concept Snapshot

Stack using linked list:
- Push: create new node, point next to head, update head
- Pop: remove head, update head to next
- Head always points to top of stack
- Empty stack when head is None
- Operations run in O(1) time

Full Transcript

This visualization shows how a stack is implemented using a linked list. Push operation adds a new node at the head of the list, making it the top of the stack. Pop operation removes the head node and moves the head pointer to the next node. The execution table traces each push and pop step, showing the nodes in the list and pointer changes. The variable tracker follows the head pointer and stack size after each operation. Key moments clarify why push adds at head, what happens when popping empty stack, and why pop updates head to next. The visual quiz tests understanding of stack state at different steps. This method ensures fast push and pop operations with simple pointer updates.

Practice

1. What is the main advantage of implementing a stack using a linked list instead of an array?

easy

A. It allows random access to elements

B. It uses less memory than an array

C. The stack can grow dynamically without a fixed size limit

D. It is easier to sort the stack elements

Solution

1. Step 1: Understand stack size limitation in arrays

   Arrays have fixed size, so stacks implemented with arrays have a maximum capacity.

2. Step 2: Linked list dynamic size property

   Linked lists can grow or shrink dynamically by adding or removing nodes, so stack size is not fixed.

3. Final Answer:

   The stack can grow dynamically without a fixed size limit -> Option C

4. Quick Check:

   Dynamic size = Advantage of linked list stack [OK]

Hint: Linked list stacks grow dynamically, arrays don't [OK]

Common Mistakes:

• Thinking linked list uses less memory always
• Confusing stack with queue behavior
• Assuming random access is possible in linked list

2. Which of the following Rust code snippets correctly defines a node struct for a linked list stack?

easy

A. struct Node { data: i32, next: Option }

B. struct Node { data: i32, next: Node }

C. struct Node { data: i32, next: &Node }

D. struct Node { data: i32, next: Box<Node> }

Solution

1. Step 1: Understand Rust ownership and recursive types

   Recursive types like linked lists require indirection using Box and Option for nullable pointers.

2. Step 2: Analyze each option

   struct Node { data: i32, next: Option } uses Option which allows nullable next pointer; struct Node { data: i32, next: Node } and struct Node { data: i32, next: &Node } are invalid due to recursive type without indirection; struct Node { data: i32, next: Box<Node> } misses Option, so no null pointer.

3. Final Answer:

   struct Node { data: i32, next: Option } -> Option A

4. Quick Check:

   Option = correct linked list pointer [OK]

Hint: Use Option for nullable next in Rust [OK]

Common Mistakes:

• Omitting Option causing infinite size error
• Using references (&Node) without lifetime
• Using Box<Node> without Option for nullable

3. Consider the following Rust code for pushing elements onto a linked list stack:

struct Node {
    data: i32,
    next: Option,
}

struct Stack {
    head: Option,
}

impl Stack {
    fn push(&mut self, val: i32) {
        let new_node = Box::new(Node { data: val, next: self.head.take() });
        self.head = Some(new_node);
    }
}

fn main() {
    let mut stack = Stack { head: None };
    stack.push(10);
    stack.push(20);
    stack.push(30);
    // What is the top element's data now?
    println!("{}", stack.head.as_ref().unwrap().data);
}

medium

A. 30

B. 20

C. 10

D. None

Solution

1. Step 1: Trace push operations

   Push 10: head points to node with data 10; Push 20: head points to node with data 20, next is 10; Push 30: head points to node with data 30, next is 20.

2. Step 2: Identify top element

   After pushes, top element is the head node's data, which is 30.

3. Final Answer:

   30 -> Option A

4. Quick Check:

   Last pushed = top element = 30 [OK]

Hint: Top is last pushed element in stack [OK]

Common Mistakes:

• Confusing order of nodes in linked list
• Assuming head points to bottom element
• Not using take() causing borrow errors

4. The following Rust code for popping an element from a linked list stack has an error. What is the error?

impl Stack {
    fn pop(&mut self) -> Option<i32> {
        if self.head.is_none() {
            return None;
        }
        let node = self.head.unwrap();
        self.head = node.next;
        Some(node.data)
    }
}

medium

A. Missing lifetime annotations on struct

B. Not checking if stack is empty before pop

C. Returning wrong data type from pop

D. Using unwrap() on Option without handling ownership

Solution

1. Step 1: Analyze unwrap() usage on self.head

   unwrap() consumes the Option, but self.head is borrowed mutably, causing ownership error.

2. Step 2: Correct way is to use take() to move ownership

   Using self.head.take() moves ownership out safely, allowing access to node and updating head.

3. Final Answer:

   Using unwrap() on Option without handling ownership -> Option D

4. Quick Check:

   unwrap() consumes Option, use take() instead [OK]

Hint: Use take() to move Option ownership safely [OK]

Common Mistakes:

• Using unwrap() causing borrow checker errors
• Ignoring empty stack check
• Confusing references and ownership

5. You want to implement a function reverse_stack that reverses the elements of a linked list stack without using extra data structures. Which approach correctly achieves this in Rust?

hard

A. Iteratively pop elements and push them onto a new stack, then replace original stack

B. Recursively pop elements, reverse the rest, then push popped element back

C. Traverse linked list and swap data values between nodes from head to tail

D. Use a vector to collect elements, reverse vector, then rebuild stack

Solution

1. Step 1: Understand constraints - no extra data structures allowed

   Options A and D use extra stacks or vectors, so they violate constraints.

2. Step 2: Recursive approach explanation

   Recursively pop elements until stack is empty, then push elements back in reverse order, effectively reversing stack without extra storage.

3. Step 3: Swapping data values is complex and error-prone

   Traverse linked list and swap data values between nodes from head to tail requires traversal and swapping data, which is complicated and not idiomatic in Rust linked lists.

4. Final Answer:

   Recursively pop elements, reverse the rest, then push popped element back -> Option B

5. Quick Check:

   Recursion reverses stack without extra structures [OK]

Hint: Use recursion to reverse stack without extra storage [OK]

Common Mistakes:

• Using extra data structures despite constraints
• Trying to swap node data directly
• Ignoring ownership rules in recursion