Linked List

Linked lists in Rust require careful handling due to ownership rules. Rust doesn't have built-in linked list types in the standard library (though std::collections::LinkedList exists), so implementing custom linked lists is a common exercise.

Basic Node Structure

#![allow(unused)]
fn main() {
#[derive(Debug)]
struct Node<T> {
    data: T,
    next: Option<Box<Node<T>>>,
}

impl<T> Node<T> {
    fn new(data: T) -> Self {
        Node {
            data,
            next: None,
        }
    }
}
}

Singly Linked List with Head and Tail

Complete Implementation with Tail Pointer

Note: Maintaining a tail pointer with Box<Node<T>> requires careful handling. The implementation below uses raw pointers for the tail, which requires unsafe code. For a safer alternative, see the simpler implementation without tail pointer below.

#![allow(unused)]
fn main() {
use std::ptr;

struct LinkedList<T> {
    head: Option<Box<Node<T>>>,
    tail: *mut Node<T>,  // Raw pointer for tail (requires unsafe)
    len: usize,
}

impl<T> LinkedList<T> {
    fn new() -> Self {
        LinkedList {
            head: None,
            tail: ptr::null_mut(),
            len: 0,
        }
    }

    // O(1) - Add to front
    fn push_front(&mut self, data: T) {
        let was_empty = self.head.is_none();
        let new_node = Box::new(Node {
            data,
            next: self.head.take(),
        });
        
        // Get raw pointer before boxing
        let raw = Box::into_raw(new_node);
        
        // If list was empty, new node is also the tail
        if was_empty {
            self.tail = raw;
        }
        
        self.head = Some(unsafe { Box::from_raw(raw) });
        self.len += 1;
    }

    // O(1) - Add to back (optimized with tail)
    fn push_back(&mut self, data: T) {
        let new_node = Box::new(Node::new(data));
        let raw = Box::into_raw(new_node);
        
        if self.head.is_none() {
            // List is empty, new node is both head and tail
            self.head = Some(unsafe { Box::from_raw(raw) });
            self.tail = raw;
        } else {
            unsafe {
                // Append to tail
                (*self.tail).next = Some(Box::from_raw(raw));
                self.tail = raw;
            }
        }
        self.len += 1;
    }

    // O(1) - Remove from front
    fn pop_front(&mut self) -> Option<T> {
        self.head.take().map(|node| {
            self.head = node.next;
            self.len -= 1;
            
            // Update tail if list is now empty
            if self.head.is_none() {
                self.tail = ptr::null_mut();
            }
            // Note: When popping front, tail pointer remains valid
            // but points to the old tail, which is still correct
            
            node.data
        })
    }

    // O(n) - Remove from back
    fn pop_back(&mut self) -> Option<T> {
        if self.head.is_none() {
            return None;
        }
        
        if self.len == 1 {
            return self.pop_front();
        }
        
        // Find second-to-last node
        let mut current = self.head.as_mut().unwrap();
        while current.next.as_ref().unwrap().next.is_some() {
            current = current.next.as_mut().unwrap();
        }
        
        let last_node = current.next.take().unwrap();
        self.tail = current.as_mut() as *mut Node<T>;
        self.len -= 1;
        Some(last_node.data)
    }

    // O(1) - Peek at front
    fn front(&self) -> Option<&T> {
        self.head.as_ref().map(|node| &node.data)
    }

    // O(1) - Peek at back (with tail pointer)
    fn back(&self) -> Option<&T> {
        if self.tail.is_null() {
            None
        } else {
            unsafe { Some(&(*self.tail).data) }
        }
    }

    // O(1) - Get length
    fn len(&self) -> usize {
        self.len
    }

    // O(1) - Check if empty
    fn is_empty(&self) -> bool {
        self.head.is_none()
    }

    // O(n) - Clear the list
    fn clear(&mut self) {
        while self.pop_front().is_some() {}
    }

    // O(n) - Check if contains value
    fn contains(&self, target: &T) -> bool 
    where
        T: PartialEq,
    {
        self.find(target).is_some()
    }

    // O(n) - Find a value
    fn find(&self, target: &T) -> Option<&T> 
    where
        T: PartialEq,
    {
        let mut current = self.head.as_ref();
        while let Some(node) = current {
            if node.data == *target {
                return Some(&node.data);
            }
            current = node.next.as_ref();
        }
        None
    }

    // O(n) - Remove first occurrence of value
    fn remove(&mut self, target: &T) -> bool 
    where
        T: PartialEq,
    {
        if self.head.is_none() {
            return false;
        }

        // Check if head needs to be removed
        if self.head.as_ref().unwrap().data == *target {
            self.pop_front();
            return true;
        }

        // Find the node before the target
        let mut current = self.head.as_mut().unwrap();
        while let Some(next) = current.next.as_mut() {
            if next.data == *target {
                let removed = current.next.take();
                current.next = removed.and_then(|n| n.next);
                self.len -= 1;
                
                // Update tail if we removed the last node
                if current.next.is_none() {
                    self.tail = current.as_mut() as *mut Node<T>;
                }
                return true;
            }
            current = current.next.as_mut().unwrap();
        }
        false
    }

    // O(n) - Get value at index
    fn get(&self, index: usize) -> Option<&T> {
        if index >= self.len {
            return None;
        }
        
        let mut current = self.head.as_ref();
        for _ in 0..index {
            current = current.unwrap().next.as_ref();
        }
        current.map(|node| &node.data)
    }

    // O(n) - Insert at index
    fn insert(&mut self, index: usize, data: T) -> bool {
        if index > self.len {
            return false;
        }

        if index == 0 {
            self.push_front(data);
            return true;
        }

        if index == self.len {
            self.push_back(data);
            return true;
        }

        // Find node at index - 1
        let mut current = self.head.as_mut().unwrap();
        for _ in 0..(index - 1) {
            current = current.next.as_mut().unwrap();
        }

        let new_node = Box::new(Node {
            data,
            next: current.next.take(),
        });
        current.next = Some(new_node);
        self.len += 1;
        true
    }

    // O(n) - Reverse the list
    fn reverse(&mut self) {
        let mut prev = None;
        let mut current = self.head.take();
        
        // Update tail to old head before reversing
        let old_head = self.head.as_ref().map(|n| n.as_ref() as *const Node<T>);
        
        while let Some(mut node) = current {
            let next = node.next.take();
            node.next = prev;
            prev = Some(node);
            current = next;
        }
        
        self.head = prev;
        
        // Update tail to old head
        if let Some(head_ptr) = old_head {
            self.tail = head_ptr as *mut Node<T>;
        } else {
            self.tail = ptr::null_mut();
        }
    }
}

impl<T> Drop for LinkedList<T> {
    fn drop(&mut self) {
        while self.pop_front().is_some() {}
    }
}
}

Alternative: Simpler Implementation Without Unsafe

For a safer implementation without raw pointers, you can use a simpler approach:

#![allow(unused)]
fn main() {
struct LinkedList<T> {
    head: Option<Box<Node<T>>>,
    len: usize,
}

impl<T> LinkedList<T> {
    fn new() -> Self {
        LinkedList {
            head: None,
            len: 0,
        }
    }

    // O(1) - Add to front
    fn push_front(&mut self, data: T) {
        let new_node = Box::new(Node {
            data,
            next: self.head.take(),
        });
        self.head = Some(new_node);
        self.len += 1;
    }

    // O(n) - Add to back (without tail pointer)
    fn push_back(&mut self, data: T) {
        let new_node = Box::new(Node::new(data));
        
        if self.head.is_none() {
            self.head = Some(new_node);
        } else {
            let mut current = self.head.as_mut().unwrap();
            while current.next.is_some() {
                current = current.next.as_mut().unwrap();
            }
            current.next = Some(new_node);
        }
        self.len += 1;
    }

    // O(1) - Remove from front
    fn pop_front(&mut self) -> Option<T> {
        self.head.take().map(|node| {
            self.head = node.next;
            self.len -= 1;
            node.data
        })
    }

    // O(n) - Remove from back
    fn pop_back(&mut self) -> Option<T> {
        if self.head.is_none() {
            return None;
        }
        
        if self.len == 1 {
            return self.pop_front();
        }
        
        let mut current = self.head.as_mut().unwrap();
        while current.next.as_ref().unwrap().next.is_some() {
            current = current.next.as_mut().unwrap();
        }
        
        let last_node = current.next.take().unwrap();
        self.len -= 1;
        Some(last_node.data)
    }

    // O(1) - Peek at front
    fn front(&self) -> Option<&T> {
        self.head.as_ref().map(|node| &node.data)
    }

    // O(n) - Peek at back (without tail pointer)
    fn back(&self) -> Option<&T> {
        let mut current = self.head.as_ref();
        while let Some(node) = current {
            if node.next.is_none() {
                return Some(&node.data);
            }
            current = node.next.as_ref();
        }
        None
    }

    fn len(&self) -> usize {
        self.len
    }

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

    fn clear(&mut self) {
        while self.pop_front().is_some() {}
    }

    fn contains(&self, target: &T) -> bool 
    where
        T: PartialEq,
    {
        self.find(target).is_some()
    }

    fn find(&self, target: &T) -> Option<&T> 
    where
        T: PartialEq,
    {
        let mut current = self.head.as_ref();
        while let Some(node) = current {
            if node.data == *target {
                return Some(&node.data);
            }
            current = node.next.as_ref();
        }
        None
    }

    fn remove(&mut self, target: &T) -> bool 
    where
        T: PartialEq,
    {
        if self.head.is_none() {
            return false;
        }

        if self.head.as_ref().unwrap().data == *target {
            self.pop_front();
            return true;
        }

        let mut current = self.head.as_mut().unwrap();
        while let Some(next) = current.next.as_mut() {
            if next.data == *target {
                let removed = current.next.take();
                current.next = removed.and_then(|n| n.next);
                self.len -= 1;
                return true;
            }
            current = current.next.as_mut().unwrap();
        }
        false
    }

    fn get(&self, index: usize) -> Option<&T> {
        if index >= self.len {
            return None;
        }
        
        let mut current = self.head.as_ref();
        for _ in 0..index {
            current = current.unwrap().next.as_ref();
        }
        current.map(|node| &node.data)
    }

    fn insert(&mut self, index: usize, data: T) -> bool {
        if index > self.len {
            return false;
        }

        if index == 0 {
            self.push_front(data);
            return true;
        }

        if index == self.len {
            self.push_back(data);
            return true;
        }

        let mut current = self.head.as_mut().unwrap();
        for _ in 0..(index - 1) {
            current = current.next.as_mut().unwrap();
        }

        let new_node = Box::new(Node {
            data,
            next: current.next.take(),
        });
        current.next = Some(new_node);
        self.len += 1;
        true
    }

    fn reverse(&mut self) {
        let mut prev = None;
        let mut current = self.head.take();
        
        while let Some(mut node) = current {
            let next = node.next.take();
            node.next = prev;
            prev = Some(node);
            current = next;
        }
        
        self.head = prev;
    }
}

impl<T> Drop for LinkedList<T> {
    fn drop(&mut self) {
        while self.pop_front().is_some() {}
    }
}
}

Traversing a Linked List

#![allow(unused)]
fn main() {
impl<T> LinkedList<T> 
where
    T: std::fmt::Display,
{
    fn traverse(&self) {
        let mut current = &self.head;
        while let Some(node) = current {
            println!("{}", node.data);
            current = &node.next;
        }
    }
}
}

Doubly Linked List

For doubly linked lists, you need Rc (Reference Counting) and RefCell to handle multiple owners:

#![allow(unused)]
fn main() {
use std::rc::{Rc, Weak};
use std::cell::RefCell;

#[derive(Debug)]
struct DoublyNode<T> {
    data: T,
    next: Option<Rc<RefCell<DoublyNode<T>>>>,
    prev: Option<Weak<RefCell<DoublyNode<T>>>>,
}

impl<T> DoublyNode<T> {
    fn new(data: T) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(DoublyNode {
            data,
            next: None,
            prev: None,
        }))
    }
}
}

Standard Methods Summary

Using Standard Library

Rust's standard library provides std::collections::LinkedList:

#![allow(unused)]
fn main() {
use std::collections::LinkedList;

let mut list: LinkedList<i32> = LinkedList::new();
list.push_front(1);
list.push_back(2);
list.push_back(3);

for item in &list {
    println!("{}", item);
}
}

Example Usage

fn main() {
    let mut list: LinkedList<i32> = LinkedList::new();
    
    // Standard operations
    list.push_back(1);
    list.push_back(2);
    list.push_back(3);
    list.push_front(0);
    
    println!("Length: {}", list.len());
    println!("Front: {:?}", list.front());
    println!("Back: {:?}", list.back());
    
    // Search and remove
    if list.contains(&2) {
        list.remove(&2);
    }
    
    // Access by index
    if let Some(value) = list.get(1) {
        println!("Value at index 1: {}", value);
    }
    
    // Insert at position
    list.insert(1, 99);
    
    // Reverse
    list.reverse();
    
    // Clear
    list.clear();
    assert!(list.is_empty());
}

Key Points

• Head and Tail: Using both pointers allows O(1) push_back and back operations
• Raw Pointers: Tail pointer requires unsafe code, but provides better performance
• Safety vs Performance: Choose between safe implementation (no tail) or unsafe (with tail)
• Ownership: Rust's ownership rules make linked lists more complex than in other languages
• Generics: Use <T> to make your linked list work with any type
• Trait Bounds: Add trait bounds like PartialEq, Display, or Debug when needed
• Box: Used for heap allocation of nodes
• Option: Used to represent nullable pointers
• Rc and RefCell: Needed for doubly linked lists or shared ownership
• Performance: std::collections::LinkedList is rarely the best choice; consider Vec or VecDeque first

Common Patterns

Iterating with References

#![allow(unused)]
fn main() {
let mut current = &list.head;
while let Some(node) = current {
    // Process node.data
    current = &node.next;
}
}

Implementing Iterator

#![allow(unused)]
fn main() {
pub struct LinkedListIter<T> {
    current: Option<Box<Node<T>>>,
}

impl<T> Iterator for LinkedListIter<T> {
    type Item = T;
    
    fn next(&mut self) -> Option<Self::Item> {
        self.current.take().map(|node| {
            self.current = node.next;
            node.data
        })
    }
}

impl<T> LinkedList<T> {
    fn into_iter(self) -> LinkedListIter<T> {
        LinkedListIter {
            current: self.head,
        }
    }
}
}