Stack Using Linked List vs Array Stack Trade-offs in DSA Rust - Trade-offs & Analysis

Mental Model

A stack stores items in order, last in first out. Using an array or linked list changes how adding and removing items works inside.

Analogy: Imagine a stack of plates. Using an array is like a fixed shelf where plates fit exactly, but you might need to move plates if full. Using a linked list is like stacking plates one by one without worrying about shelf size, but you carry each plate separately.

Array Stack: [1, 2, 3, _, _] ↑top at index 2
Linked List Stack: 3 -> 2 -> 1 -> null ↑top points to 3

Dry Run Walkthrough

Input: Push 4 onto stack with elements 1, 2, 3; then pop one element

Goal: Show how push and pop behave differently in array and linked list stacks

Step 1: Push 4 onto array stack

Array Stack: [1, 2, 3, 4, _] ↑top at index 3
Linked List Stack: 3 -> 2 -> 1 -> null ↑top points to 3

Why: Add 4 at next free index in array, top moves up

Step 2: Push 4 onto linked list stack

Array Stack: [1, 2, 3, 4, _] ↑top at index 3
Linked List Stack: 4 -> 3 -> 2 -> 1 -> null ↑top points to 4

Why: Create new node with 4, link it to old top, update top pointer

Step 3: Pop from array stack

Array Stack: [1, 2, 3, _, _] ↑top at index 2
Linked List Stack: 4 -> 3 -> 2 -> 1 -> null ↑top points to 4

Why: Remove top element by moving top index down

Step 4: Pop from linked list stack

Array Stack: [1, 2, 3, _, _] ↑top at index 2
Linked List Stack: 3 -> 2 -> 1 -> null ↑top points to 3

Why: Remove top node by moving top pointer to next node

Result:

Array Stack: [1, 2, 3, _, _] ↑top at index 2
Linked List Stack: 3 -> 2 -> 1 -> null ↑top points to 3

Annotated Code

DSA Rust

use std::fmt;

// Node for linked list stack
struct Node<T> {
    data: T,
    next: Option<Box<Node<T>>>,
}

// Linked list stack
struct LinkedListStack<T> {
    top: Option<Box<Node<T>>>,
}

impl<T> LinkedListStack<T> {
    fn new() -> Self {
        LinkedListStack { top: None }
    }

    fn push(&mut self, value: T) {
        let new_node = Box::new(Node {
            data: value,
            next: self.top.take(), // link new node to current top
        });
        self.top = Some(new_node); // update top pointer
    }

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

impl<T: fmt::Display> fmt::Display for LinkedListStack<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let mut curr = &self.top;
        while let Some(node) = curr {
            write!(f, "{} -> ", node.data)?;
            curr = &node.next;
        }
        write!(f, "null")
    }
}

// Array stack
struct ArrayStack<T> {
    data: Vec<T>,
    capacity: usize,
}

impl<T> ArrayStack<T> {
    fn new(capacity: usize) -> Self {
        ArrayStack {
            data: Vec::with_capacity(capacity),
            capacity,
        }
    }

    fn push(&mut self, value: T) -> Result<(), &str> {
        if self.data.len() == self.capacity {
            return Err("Stack overflow");
        }
        self.data.push(value);
        Ok(())
    }

    fn pop(&mut self) -> Option<T> {
        self.data.pop()
    }
}

impl<T: fmt::Display> fmt::Display for ArrayStack<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        for val in &self.data {
            write!(f, "{} -> ", val)?;
        }
        write!(f, "null")
    }
}

fn main() {
    // Start with 1,2,3 in both stacks
    let mut array_stack = ArrayStack::new(5);
    array_stack.push(1).unwrap();
    array_stack.push(2).unwrap();
    array_stack.push(3).unwrap();

    let mut linked_stack = LinkedListStack::new();
    linked_stack.push(1);
    linked_stack.push(2);
    linked_stack.push(3);

    println!("Initial Array Stack: {}", array_stack);
    println!("Initial Linked List Stack: {}", linked_stack);

    // Push 4
    array_stack.push(4).unwrap();
    linked_stack.push(4);

    println!("After pushing 4:");
    println!("Array Stack: {}", array_stack);
    println!("Linked List Stack: {}", linked_stack);

    // Pop one element
    let popped_array = array_stack.pop();
    let popped_linked = linked_stack.pop();

    println!("After popping one element:");
    println!("Array Stack: {}", array_stack);
    println!("Linked List Stack: {}", linked_stack);
    println!("Popped from array stack: {:?}", popped_array);
    println!("Popped from linked list stack: {:?}", popped_linked);
}

self.top = Some(new_node); // update top pointer

update top pointer to new node for push in linked list

self.top = node.next; // move top to next node

move top pointer down to next node for pop in linked list

if self.data.len() == self.capacity { return Err("Stack overflow"); }

check for overflow before push in array stack

self.data.push(value);

add value at end of array for push

self.data.pop()

remove last element from array for pop

Output

Initial Array Stack: 1 -> 2 -> 3 -> null

Initial Linked List Stack: 3 -> 2 -> 1 -> null

After pushing 4:

Array Stack: 1 -> 2 -> 3 -> 4 -> null

Linked List Stack: 4 -> 3 -> 2 -> 1 -> null

After popping one element:

Array Stack: 1 -> 2 -> 3 -> null

Linked List Stack: 3 -> 2 -> 1 -> null

Popped from array stack: Some(4)

Popped from linked list stack: Some(4)

Complexity Analysis

Time: O(1) for push and pop in both array and linked list stacks because operations happen at one end only

Space: O(n) for both, but array stack uses contiguous memory while linked list uses extra memory for pointers

vs Alternative: Array stack is faster in memory access but fixed size; linked list stack is flexible size but uses extra memory and may have slower access

Edge Cases

Push on full array stack

Push returns error 'Stack overflow' and does not add element

DSA Rust

if self.data.len() == self.capacity { return Err("Stack overflow"); }

Pop from empty stack

Pop returns None safely without error

DSA Rust

self.top.take().map(...) and self.data.pop() handle empty cases

Push and pop single element

Stack correctly adds and removes the single element

DSA Rust

self.top = Some(new_node) and self.top = node.next

When to Use This Pattern

When a problem needs last-in-first-out order with dynamic size or fixed size constraints, choose linked list stack for flexible size or array stack for faster access and fixed capacity.

Common Mistakes

Mistake: Not checking for array stack overflow before push
Fix: Add capacity check before pushing to array stack

Mistake: Forgetting to update top pointer after pop in linked list
Fix: Assign top to next node after removing current top

Summary

Stack using linked list or array both store items last-in-first-out but differ in memory and size handling.

Use array stack when size is known and speed is important; use linked list stack when size varies and flexibility is needed.

The key insight is that array stack uses fixed contiguous space with index, linked list stack uses nodes linked by pointers allowing dynamic size.

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