Stack Implementation Using Linked List in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output after pushing and popping elements?

Consider a stack implemented using a linked list. The following operations are performed in order:

push(10), push(20), push(30), pop(), push(40), pop()

What is the printed state of the stack after these operations?

DSA Rust

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

struct Stack {
    top: Option<Box<Node>>,
}

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

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

    fn pop(&mut self) -> Option<i32> {
        self.top.take().map(|node| {
            self.top = node.next;
            node.data
        })
    }

    fn print_stack(&self) {
        let mut current = &self.top;
        while let Some(node) = current {
            print!("{} -> ", node.data);
            current = &node.next;
        }
        print!("null\n");
    }
}

fn main() {
    let mut stack = Stack::new();
    stack.push(10);
    stack.push(20);
    stack.push(30);
    stack.pop();
    stack.push(40);
    stack.pop();
    stack.print_stack();
}

A 40 -> 20 -> 10 -> null

B 10 -> null

C 30 -> 20 -> 10 -> null

D 20 -> 10 -> null

💡 Hint

Remember that pop removes the top element and push adds a new top.

After pushing 10, 20, 30, the stack is 30 -> 20 -> 10 -> null. Pop removes 30, stack becomes 20 -> 10 -> null. Push 40 adds 40 on top: 40 -> 20 -> 10 -> null. Pop removes 40, stack returns to 20 -> 10 -> null.

🧠 Conceptual

intermediate

What is the time complexity of push and pop operations in a linked list stack?

In a stack implemented using a linked list, what is the time complexity of the push and pop operations?

A Push is O(n), pop is O(1)

B Both push and pop are O(1)

C Push is O(1), pop is O(n)

D Both push and pop are O(n)

💡 Hint

Think about how many nodes you need to traverse for each operation.

Both push and pop operate only at the top of the stack, which is the head of the linked list. They do not require traversal, so both are O(1).

🔧 Debug

advanced

Identify the error in this pop method implementation

The following Rust code attempts to implement the pop method for a linked list stack. What error will it cause when compiled or run?

DSA Rust

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

A Runtime panic: unwrap on None value

B Logical error: pop does not remove the top element

C Compile error: cannot move out of borrowed content

D No error, works correctly

💡 Hint

Consider ownership rules when using unwrap on Option inside a method with &mut self.

Calling unwrap() on self.top moves the Box out of the Option, but self.top is borrowed mutably, so Rust forbids moving out of borrowed content. This causes a compile error.

📝 Syntax

advanced

Which option correctly implements push method for linked list stack in Rust?

Select the correct Rust code snippet that implements the push method for a linked list stack.

A

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

B

fn push(&mut self, data: i32) {
    self.top = Some(Box::new(Node { data, next: self.top }));
}

C

fn push(&mut self, data: i32) {
    let new_node = Node { data, next: self.top.take() };
    self.top = new_node;
}

D

fn push(&mut self, data: i32) {
    let new_node = Box::new(Node { data, next: self.top });
    self.top = Some(new_node);
}

💡 Hint

Remember to take ownership of the current top node before linking it.

Option A correctly uses self.top.take() to move the current top out safely and then assigns the new node as the new top wrapped in Some(Box::new(...)). Option A tries to use self.top directly without take(), causing ownership errors. Option A assigns a Node directly to self.top which expects Option>. Option A uses self.top without take(), causing ownership errors.

🚀 Application

expert

What is the stack state after a sequence of mixed operations?

Given a linked list stack initially empty, the following operations are performed:

push(5), push(15), pop(), push(25), push(35), pop(), pop(), push(45)

What is the printed state of the stack after these operations?

DSA Rust

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

struct Stack {
    top: Option<Box<Node>>,
}

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

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

    fn pop(&mut self) -> Option<i32> {
        self.top.take().map(|node| {
            self.top = node.next;
            node.data
        })
    }

    fn print_stack(&self) {
        let mut current = &self.top;
        while let Some(node) = current {
            print!("{} -> ", node.data);
            current = &node.next;
        }
        print!("null\n");
    }
}

fn main() {
    let mut stack = Stack::new();
    stack.push(5);
    stack.push(15);
    stack.pop();
    stack.push(25);
    stack.push(35);
    stack.pop();
    stack.pop();
    stack.push(45);
    stack.print_stack();
}

A 45 -> 5 -> null

B 25 -> 5 -> null

C 15 -> 5 -> null

D 35 -> 25 -> 5 -> null

💡 Hint

Track each push and pop carefully, updating the top of the stack.

Operations step-by-step:
push(5): 5 -> null
push(15): 15 -> 5 -> null
pop(): removes 15, stack is 5 -> null
push(25): 25 -> 5 -> null
push(35): 35 -> 25 -> 5 -> null
pop(): removes 35, stack is 25 -> 5 -> null
pop(): removes 25, stack is 5 -> null
push(45): 45 -> 5 -> null

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