Algorithms and Data Structures in Rust: A Practical Guide

Introduction: Why Rust for Algorithms?

Rust is a modern systems programming language that combines the high performance of C/C++ with memory safety. For learning algorithms and data structures, Rust is particularly good because:

• Ownership control forces you to explicitly think about memory management
• Safety — the compiler prevents many runtime errors
• Speed — Rust compiles to machine code, which is important for performance-critical algorithms

In this article, we will examine the implementation of four basic structures and algorithms in Rust with practical code examples.

1. Linked List

One of the classic data structures. In Rust, its implementation requires using Box for heap memory allocation and Option to represent the absence of a node.

Singly Linked List Implementation

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

// The list itself#[derive(Debug)]struct LinkedList<T> {    head: Option<Box<Node<T>>>,}

impl<T> LinkedList<T> {    // Create an empty list    fn new() -> Self {        LinkedList { head: None }    }

    // Add an element to the front    fn push_front(&mut self, value: T) {        let new_node = Box::new(Node {            value,            next: self.head.take(),        });        self.head = Some(new_node);    }

    // Remove an element from the front    fn pop_front(&mut self) -> Option<T> {        self.head.take().map(|node| {            self.head = node.next;            node.value        })    }}

fn main() {    let mut list = LinkedList::new();    list.push_front(10);    list.push_front(20);    list.push_front(30);    println!("{:?}", list); // LinkedList { head: Some(Node { value: 30, next: ... }) }        let popped = list.pop_front();    println!("Removed: {:?}", popped); // Removed: Some(30)    println!("List now: {:?}", list);}

What is happening here:

• Box<Node> — a pointer to a node on the heap
• Option — either there is a node (Some) or there isn't (None)
• take() — takes the value out of Option, leaving None in its place

2. Binary Search Tree (BST)

A tree is a hierarchical structure. In a binary search tree, each node has a left and right child, where the left child is smaller than the root and the right child is larger.

BST Implementation

use std::cmp::Ordering;

#[derive(Debug)]struct TreeNode<T> {    value: T,    left: Option<Box<TreeNode<T>>>,    right: Option<Box<TreeNode<T>>>,}

#[derive(Debug)]struct BinarySearchTree<T> {    root: Option<Box<TreeNode<T>>>,}

impl<T: Ord> BinarySearchTree<T> {    fn new() -> Self {        BinarySearchTree { root: None }    }

    // Insert an element    fn insert(&mut self, value: T) {        let mut current = &mut self.root;        while let Some(node) = current {            match value.cmp(&node.value) {                Ordering::Less => current = &mut node.left,                Ordering::Greater => current = &mut node.right,                Ordering::Equal => return, // ignore duplicates            }        }        *current = Some(Box::new(TreeNode {            value,            left: None,            right: None,        }));    }

    // Search for an element    fn contains(&self, value: &T) -> bool {        let mut current = &self.root;        while let