Stack Implementation Using Linked List in DSA Rust

Mental Model

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

Analogy: Imagine stacking plates one on top of another. You can only add a new plate on top or take the top plate off. Each plate knows which plate is below it, but not the ones below that.

Top -> [Node1] -> [Node2] -> [Node3] -> null
          ↑
        Stack top

Dry Run Walkthrough

Input: Push values 10, then 20, then 30 onto an empty stack; then pop one value

Goal: Show how the stack grows and shrinks using linked list nodes

Step 1: Push 10: create node with 10, point top to it

Top -> [10] -> null
          ↑

Why: Start stack with first element at top

Step 2: Push 20: create node with 20, point it to current top (10), update top to new node

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

Why: New item goes on top, links to previous top

Step 3: Push 30: create node with 30, point it to current top (20), update top to new node

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

Why: Add new item on top, keep chain intact

Step 4: Pop: remove top node (30), update top to next node (20)

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

Why: Remove top item, top moves down one node

Result:

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

Annotated Code

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

// Define a node in the linked list
struct Node {
    value: i32,
    next: Option<Rc<RefCell<Node>>>,
}

// Stack implemented using linked list
struct Stack {
    top: Option<Rc<RefCell<Node>>>,
}

impl Stack {
    fn new() -> Self {
        Stack { top: None }
    }

    // Push value onto stack
    fn push(&mut self, val: i32) {
        let new_node = Rc::new(RefCell::new(Node {
            value: val,
            next: self.top.clone(), // link new node to current top
        }));
        self.top = Some(new_node); // update top to new node
    }

    // Pop value from stack
    fn pop(&mut self) -> Option<i32> {
        match self.top.take() {
            None => None, // stack empty
            Some(node) => {
                let val = node.borrow().value;
                self.top = node.borrow().next.clone(); // move top down
                Some(val)
            }
        }
    }

    // Print stack from top to bottom
    fn print(&self) {
        let mut current = self.top.clone();
        let mut output = String::new();
        while let Some(node) = current {
            output.push_str(&format!("{} -> ", node.borrow().value));
            current = node.borrow().next.clone();
        }
        output.push_str("null");
        println!("{}", output);
    }
}

fn main() {
    let mut stack = Stack::new();
    stack.push(10);
    stack.push(20);
    stack.push(30);
    stack.print();
    let popped = stack.pop();
    println!("Popped value: {}", popped.unwrap());
    stack.print();
}

let new_node = Rc::new(RefCell::new(Node { value: val, next: self.top.clone() }));

Create new node pointing to current top to link stack

self.top = Some(new_node);

Update top pointer to new node -- push operation

match self.top.take() { ... }

Remove top node safely for pop operation

self.top = node.borrow().next.clone();

Move top pointer down to next node after pop

Output

30 -> 20 -> 10 -> null

Popped value: 30

20 -> 10 -> null

Complexity Analysis

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

Space: O(n) for n elements because each element is a separate node in the linked list

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 Rust

match self.top.take() { None => None, ... }

Push onto empty stack

Creates first node and sets top correctly

DSA Rust

self.top = Some(new_node);

When to Use This Pattern

When you need a stack with dynamic size and fast push/pop without resizing, use linked list stack to manage elements efficiently.

Common Mistakes

Mistake: Not updating 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: Losing reference to nodes causing memory leaks or invalid state
Fix: Use Rc and RefCell to manage shared ownership and mutability safely

Summary

Implements a stack using a linked list 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 keep the top pointer updated to the newest node for push and to the next node for pop.

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