Algorithmes et structures de données en Rust : guide pratique

Introduction : pourquoi Rust pour les algorithmes ?

Rust est un langage de programmation système moderne qui combine les hautes performances du C/C++ avec la sécurité mémoire. Pour l'étude des algorithmes et des structures de données, Rust est particulièrement adapté car :

• Le contrôle de possession (ownership) oblige à réfléchir explicitement à la gestion de la mémoire
• La sécurité — le compilateur empêche de nombreuses erreurs d'exécution
• La vitesse — Rust se compile en code machine, ce qui est important pour les algorithmes performants

Dans cet article, nous allons détailler l'implémentation de quatre structures et algorithmes de base en Rust avec des exemples de code pratiques.

1. Liste chaînée (Linked List)

Une des structures de données classiques. En Rust, son implémentation nécessite l'utilisation de Box pour allouer de la mémoire sur le tas et de Option pour représenter l'absence de nœud.

Implémentation d'une liste simplement chaînée

// Définition du nœud de la liste#[derive(Debug)]struct Node<T> {    value: T,    next: Option<Box<Node<T>>>,}

// La liste elle-même#[derive(Debug)]struct LinkedList<T> {    head: Option<Box<Node<T>>>,}

impl<T> LinkedList<T> {    // Création d'une liste vide    fn new() -> Self {        LinkedList { head: None }    }

    // Ajout d'un élément au début    fn push_front(&mut self, value: T) {        let new_node = Box::new(Node {            value,            next: self.head.take(),        });        self.head = Some(new_node);    }

    // Suppression d'un élément du début    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!("Supprimé : {:?}", popped); // Supprimé : Some(30)    println!("Liste maintenant : {:?}", list);}

Ce qui se passe ici :

• Box<Node> — pointeur vers un nœud sur le tas
• Option — soit il y a un nœud (Some), soit il n'y en a pas (None)
• take() — prend la valeur de Option, laissant None

2. Arbre binaire de recherche (Binary Search Tree)

Un arbre est une structure hiérarchique. Dans un arbre binaire de recherche, chaque nœud a un enfant gauche et un enfant droit, le gauche étant plus petit que la racine et le droit plus grand.

Implémentation d'un BST

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 }    }

    // Insertion d'un élément    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, // on ignore les doublons            }        }        *current = Some(Box::new(TreeNode {            value,            left: None,            right: None,        }));    }

    // Recherche d'un élément    fn contains(&self, value: &T) -> bool {        let mut current = &self.root;        while let