Stack Implementation (Using Linked List)

A stack can also be implemented using a linked list, where elements are added and removed from the head of the list. This naturally preserves the Last In, First Out (LIFO) behavior of a stack.

Using a linked list avoids resizing costs and allows stack growth without requiring contiguous memory.

Key Idea

To implement a stack with a linked list:

• The top of the stack corresponds to the head of the list
• Push → insert at the head
• Pop → remove from the head

Push / Pop
   ↓
[Top] → [2] → [1] → null

All core operations run in constant time.

Stack Operations

The linked-list stack supports:

• Push - insert at the head
• Pop - remove from the head
• Peek - read the head value
• Is Empty - check if the stack is empty

Rust Representation

This implementation uses a singly linked list, similar to the one you already introduced, but specialized for stack behavior.

Rust Implementation

#[derive(Debug)]
struct Node<T> {
    value: T,
    next: Option<Box<Node<T>>>,
}

#[derive(Debug)]
pub struct Stack<T> {
    head: Option<Box<Node<T>>>,
}

impl<T> Stack<T> {
    pub fn new() -> Self {
        Stack { head: None }
    }

    pub fn push(&mut self, value: T) {
        let new_node = Box::new(Node {
            value,
            next: self.head.take(),
        });

        self.head = Some(new_node);
    }

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

    pub fn peek(&self) -> Option<&T> {
        self.head.as_ref().map(|node| &node.value)
    }

    pub fn is_empty(&self) -> bool {
        self.head.is_none()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn stack_works() {
        let mut stack = Stack::new();

        assert!(stack.is_empty());

        stack.push(1);
        stack.push(2);
        stack.push(3);

        assert_eq!(stack.peek(), Some(&3));
        assert_eq!(stack.pop(), Some(3));
        assert_eq!(stack.pop(), Some(2));
        assert_eq!(stack.pop(), Some(1));
        assert!(stack.is_empty());
    }
}

Example Usage

fn main() {
    let mut stack = Stack::new();

    stack.push(10);
    stack.push(20);
    stack.push(30);

    println!("Top: {:?}", stack.peek()); // Some(30)

    while let Some(value) = stack.pop() {
        println!("Popped: {}", value);
    }
}

Output:

Top: Some(30)
Popped: 30
Popped: 20
Popped: 10

Time and Space Complexity

Time Complexity

Space Complexity

Vec Stack vs Linked List Stack

When to Use a Linked List Stack

Use a linked-list stack when:

• Stack size is highly dynamic
• You want guaranteed O(1) push/pop
• Memory fragmentation is acceptable

In practice, Vec is usually preferred unless constraints demand otherwise.

Summary

• Stack behavior maps naturally to a linked list
• Head insertion/removal gives O(1) operations
• Simple and predictable performance
• Slightly higher memory cost than Vec

Playground Links

Rust - Stack Implementation (Using Linked List)