Stack Using Linked List vs Array Stack Trade-offs in DSA Rust - Build Both Approaches

Stack Using Linked List vs Array Stack Trade-offs

📖 Scenario: Imagine you are building a simple program to manage a stack of books. You want to try two ways to store the books: using a linked list and using an array. Each book is represented by its title as a string.This will help you understand the differences between these two stack methods.

🎯 Goal: You will create two stacks: one using a linked list and one using an array. You will push some books onto each stack and then pop one book from each. Finally, you will print the remaining books in each stack to see how they look.

📋 What You'll Learn

Create a linked list stack with push and pop methods

Create an array stack with push and pop methods

Push three book titles onto each stack

Pop one book from each stack

Print the remaining books in each stack

💡 Why This Matters

🌍 Real World

Stacks are used in undo features, expression evaluation, and backtracking algorithms. Knowing different implementations helps optimize performance and memory.

💼 Career

Understanding stack implementations and their trade-offs is important for software engineers working on system design, embedded systems, and performance-critical applications.

1

Create a linked list stack with push and pop methods

Create a struct called Node with a title field of type String and a next field of type Option. Then create a struct called LinkedListStack with a head field of type Option. Implement methods push(&mut self, title: String) and pop(&mut self) -> Option<String> for LinkedListStack.

DSA Rust

# Define Node and LinkedListStack structs
# Implement push and pop methods for LinkedListStack
# Your code here

Hint

Think of Node as a book with a title and a link to the next book. The LinkedListStack keeps track of the top book with head.

2

Create an array stack with push and pop methods

Create a struct called ArrayStack with a field items of type Vec<String>. Implement methods push(&mut self, title: String) and pop(&mut self) -> Option<String> for ArrayStack.

DSA Rust

struct Node {
    title: String,
    next: Option>,
}

struct LinkedListStack {
    head: Option>,
}

impl LinkedListStack {
    fn new() -> Self {
        LinkedListStack { head: None }
    }

    fn push(&mut self, title: String) {
        let new_node = Box::new(Node {
            title,
            next: self.head.take(),
        });
        self.head = Some(new_node);
    }

    fn pop(&mut self) -> Option {
        self.head.take().map(|node| {
            self.head = node.next;
            node.title
        })
    }
}

// Define ArrayStack struct
// Implement push and pop methods for ArrayStack
// Your code here

Hint

Think of ArrayStack as a stack of books stored in a list. You add books to the end and remove from the end.

3

Push three books onto each stack and pop one book from each

Create mutable variables linked_stack and array_stack as new instances of LinkedListStack and ArrayStack respectively. Push the books "Book A", "Book B", and "Book C" onto both stacks using the push method. Then pop one book from each stack using the pop method.

DSA Rust

struct Node {
    title: String,
    next: Option>,
}

struct LinkedListStack {
    head: Option>,
}

impl LinkedListStack {
    fn new() -> Self {
        LinkedListStack { head: None }
    }

    fn push(&mut self, title: String) {
        let new_node = Box::new(Node {
            title,
            next: self.head.take(),
        });
        self.head = Some(new_node);
    }

    fn pop(&mut self) -> Option {
        self.head.take().map(|node| {
            self.head = node.next;
            node.title
        })
    }
}

struct ArrayStack {
    items: Vec,
}

impl ArrayStack {
    fn new() -> Self {
        ArrayStack { items: Vec::new() }
    }

    fn push(&mut self, title: String) {
        self.items.push(title);
    }

    fn pop(&mut self) -> Option {
        self.items.pop()
    }
}

// Create linked_stack and array_stack
// Push "Book A", "Book B", "Book C" onto both
// Pop one book from each
// Your code here

Hint

Remember to create new stacks first, then push books in order, and finally pop one book from each.

4

Print the remaining books in each stack

Add a function print_linked_list_stack(stack: &LinkedListStack) that prints the titles from top to bottom separated by -> and ending with None. Add a function print_array_stack(stack: &ArrayStack) that prints the titles from top to bottom separated by -> and ending with None. Call these functions in main to print the remaining books in linked_stack and array_stack.

DSA Rust

struct Node {
    title: String,
    next: Option>,
}

struct LinkedListStack {
    head: Option>,
}

impl LinkedListStack {
    fn new() -> Self {
        LinkedListStack { head: None }
    }

    fn push(&mut self, title: String) {
        let new_node = Box::new(Node {
            title,
            next: self.head.take(),
        });
        self.head = Some(new_node);
    }

    fn pop(&mut self) -> Option {
        self.head.take().map(|node| {
            self.head = node.next;
            node.title
        })
    }
}

struct ArrayStack {
    items: Vec,
}

impl ArrayStack {
    fn new() -> Self {
        ArrayStack { items: Vec::new() }
    }

    fn push(&mut self, title: String) {
        self.items.push(title);
    }

    fn pop(&mut self) -> Option {
        self.items.pop()
    }
}

fn print_linked_list_stack(stack: &LinkedListStack) {
    // Your code here
}

fn print_array_stack(stack: &ArrayStack) {
    // Your code here
}

fn main() {
    let mut linked_stack = LinkedListStack::new();
    let mut array_stack = ArrayStack::new();

    linked_stack.push("Book A".to_string());
    linked_stack.push("Book B".to_string());
    linked_stack.push("Book C".to_string());

    array_stack.push("Book A".to_string());
    array_stack.push("Book B".to_string());
    array_stack.push("Book C".to_string());

    linked_stack.pop();
    array_stack.pop();

    print_linked_list_stack(&linked_stack);
    print_array_stack(&array_stack);
}

Hint

Traverse the linked list from head to end printing titles. For the array stack, print items from last to first.

Practice

1. Which of the following is a key advantage of using a linked list to implement a stack compared to using an array?

easy

A. Faster access to elements by index

B. Simpler to implement in all languages

C. Uses less memory overall

D. Dynamic size without needing to resize

Solution

1. Step 1: Understand stack size behavior

   Arrays have fixed size or require resizing, linked lists grow dynamically as needed.

2. Step 2: Compare access and memory

   Linked lists do not provide faster index access and may use more memory due to pointers.

3. Final Answer:

   Dynamic size without needing to resize -> Option D

4. Quick Check:

   Linked list stacks grow dynamically = B [OK]

Hint: Linked list stacks grow dynamically, arrays need resizing [OK]

Common Mistakes:

• Thinking linked lists have faster index access
• Assuming arrays always use less memory
• Believing linked lists are simpler to implement everywhere

2. Which Rust syntax correctly declares a stack using a vector (array stack)?

easy

A. let stack: Vec<i32> = [];

B. let stack = new Vec<i32>();

C. let mut stack: Vec<i32> = Vec::new();

D. let mut stack = Vec<i32>::empty();

Solution

1. Step 1: Recall Rust vector initialization

   Correct syntax uses Vec::new() to create an empty vector.

2. Step 2: Check each option

   B uses invalid 'new' keyword, C uses array syntax, D uses non-existent empty() method.

3. Final Answer:

   let mut stack: Vec<i32> = Vec::new(); -> Option C

4. Quick Check:

   Vec::new() creates empty vector = A [OK]

Hint: Use Vec::new() with mut for stack vector in Rust [OK]

Common Mistakes:

• Using 'new' keyword instead of Vec::new()
• Trying to assign array literal directly
• Using non-existent Vec methods

3. What will be the output of the following Rust code using a linked list stack?

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

fn main() {
    let mut stack: Option = None;
    // Push 10
    stack = Some(Box::new(Node { value: 10, next: stack }));
    // Push 20
    stack = Some(Box::new(Node { value: 20, next: stack }));
    // Pop top
    if let Some(top) = stack {
        println!("{}", top.value);
        stack = top.next;
    }
    // Print new top
    if let Some(top) = &stack {
        println!("{}", top.value);
    }
}

medium

A. 20
10

B. 10
20

C. 10
10

D. 20
20

Solution

1. Step 1: Trace push operations

   Push 10: stack points to node with value 10. Push 20: stack points to node with value 20, next points to 10.

2. Step 2: Trace pop and prints

   Pop prints 20, then stack moves to next node (10). Next print prints 10.

3. Final Answer:

   20 10 -> Option A

4. Quick Check:

   Stack top after push: 20, after pop: 10 [OK]

Hint: Top is last pushed, pop removes top, next is previous [OK]

Common Mistakes:

• Confusing push order and print order
• Printing after pop without updating stack
• Misunderstanding Option and Box usage

4. Identify the bug in this Rust code implementing a stack with an array (Vec) and fix it:

fn main() {
    let mut stack: Vec<i32> = Vec::new();
    stack.push(1);
    stack.push(2);
    let top = stack.pop();
    println!("Top element: {}", top.unwrap());
    println!("Next element: {}", stack.pop().unwrap());
    println!("Empty pop: {}", stack.pop().unwrap());
}

medium

A. Calling unwrap() on empty pop causes panic; check Option before unwrap

B. Vec::new() should be Vec::with_capacity()

C. Use stack.peek() instead of pop() to view top

D. stack.push() should be called after pop()

Solution

1. Step 1: Analyze pop calls and unwrap

   First two pops succeed, third pop returns None; unwrap on None panics.

2. Step 2: Fix by checking Option before unwrap

   Use if let or match to safely handle empty stack before unwrap.

3. Final Answer:

   Calling unwrap() on empty pop causes panic; check Option before unwrap -> Option A

4. Quick Check:

   Pop returns Option, unwrap on None panics [OK]

Hint: Always check Option before unwrap after pop [OK]

Common Mistakes:

• Ignoring possibility of empty stack pop
• Thinking Vec::with_capacity fixes panic
• Using peek instead of pop changes logic

5. You need to implement a stack in Rust for a program where the maximum number of elements is unknown and can grow large unpredictably. Which implementation is better and why?

1. Array stack using Vec with occasional resizing
2. Linked list stack with dynamic nodes

hard

A. Array stack is better because it uses less memory per element and faster cache access

B. Linked list stack is better because it grows dynamically without resizing overhead

C. Array stack is better because resizing never happens in Rust Vec

D. Linked list stack is better because it uses contiguous memory for faster access

Solution

1. Step 1: Consider unknown large size and growth

   Linked list stacks grow node by node without resizing, arrays resize which can be costly.

2. Step 2: Compare memory and speed trade-offs

   Arrays have better cache but resizing overhead; linked lists avoid resizing but use extra memory per node.

3. Step 3: Choose best fit for unpredictable large growth

   Linked list avoids resizing delays and can handle unpredictable growth smoothly.

4. Final Answer:

   Linked list stack is better because it grows dynamically without resizing overhead -> Option B

5. Quick Check:

   Dynamic growth without resizing = Linked list stack [OK]

Hint: For unknown large size, linked list avoids resizing delays [OK]

Common Mistakes:

• Assuming Vec never resizes
• Ignoring memory overhead of linked list nodes
• Confusing contiguous memory with linked list