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

Introduction aux algorithmes et structures de données en Rust

Le langage de programmation Rust a gagné la reconnaissance des développeurs grâce à ses hautes performances et ses garanties strictes de sécurité mémoire. Cependant, la transition vers Rust depuis d'autres langages, comme Python ou JavaScript, peut être difficile, notamment lors de l'implémentation d'algorithmes classiques et de structures de données. Dans cet article, nous verrons comment implémenter efficacement des structures de données et algorithmes de base en Rust, en tenant compte des particularités du système de possession (ownership) et d'emprunt (borrowing).

Cet article est destiné aux développeurs déjà familiers avec les bases de Rust. Nous nous concentrerons sur des exemples de code pratiques pouvant être utilisés immédiatement dans des projets réels. Tous les exemples seront accompagnés de commentaires détaillés.

Implémentation d'une liste chaînée en Rust

La liste chaînée est l'une des structures de données fondamentales. En Rust, son implémentation nécessite une attention particulière en raison des règles de possession. Examinons une liste simplement chaînée utilisant Box pour la gestion de la mémoire.

Liste simplement chaînée de base

Commençons par définir le nœud et la liste elle-même :

use std::fmt::Display;

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

#[derive(Debug)]struct LinkedList<T> {    head: Option<Box<Node<T>>>,    length: usize,}

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

    fn push_front(&mut self, value: T) {        let new_node = Box::new(Node {            value,            next: self.head.take(),        });        self.head = Some(new_node);        self.length += 1;    }

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

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

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

Notez l'utilisation de Option<Box<Node<T>>>. C'est la manière standard de créer des structures récursives en Rust, car le compilateur exige une taille connue à l'avance. La méthode take() permet d'extraire en toute sécurité une valeur d'un Option, en la remplaçant par None.

Itération sur la liste

Implémentons un itérateur pour la liste :

impl<T: Clone> LinkedList<T> {    fn iter(&self) -> LinkedListIterator<T> {        LinkedListIterator {            current: self.head.as_deref(),        }    }}

struct LinkedListIterator<T> {    current: Option<&Node<T>>,}

impl<T> Iterator for LinkedListIterator<T> {    type Item = &T;

    fn next(&mut self) -> Option<Self::Item> {        self.current.take().map(|node| {            self.current = node.next.as_deref();            &node.value        })    }}

Arbre binaire de recherche (BST) en Rust

Les arbres sont une autre structure importante. Implémentons un arbre binaire de recherche avec support de l'insertion, de la recherche et du parcours.

Structure et insertion de base

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

    fn insert(&mut self, value: T) {        let mut current = &mut self.root;        while let Some(node) = current {            if value <