Algoritmos y estructuras de datos en Rust: guía práctica

Introducción a algoritmos y estructuras de datos en Rust

El lenguaje de programación Rust ha ganado reconocimiento entre los desarrolladores gracias a su alto rendimiento y estrictas garantías de seguridad de memoria. Sin embargo, la transición a Rust desde otros lenguajes como Python o JavaScript puede ser compleja, especialmente al implementar algoritmos y estructuras de datos clásicos. En este artículo, exploraremos cómo implementar eficientemente estructuras de datos básicas y algoritmos en Rust, teniendo en cuenta las particularidades del sistema de ownership y borrowing.

El artículo está dirigido a desarrolladores que ya conocen los fundamentos de Rust. Nos centraremos en ejemplos prácticos de código que se pueden usar inmediatamente en proyectos reales. Todos los ejemplos incluirán comentarios detallados.

Implementación de una lista enlazada en Rust

La lista enlazada es una de las estructuras de datos fundamentales. En Rust, su implementación requiere especial atención debido a las reglas de ownership. Consideremos una lista simplemente enlazada usando Box para la gestión de memoria.

Lista simplemente enlazada básica

Empecemos definiendo el nodo y la lista:

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

Observa el uso de Option<Box<Node<T>>>. Esta es la forma estándar de crear estructuras recursivas en Rust, ya que el compilador requiere un tamaño conocido de antemano. El método take() permite extraer de forma segura un valor de Option, reemplazándolo con None.

Iteración sobre la lista

Implementemos un iterador para la lista:

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

Árbol binario de búsqueda (BST) en Rust

Los árboles son otra estructura importante. Implementemos un árbol binario de búsqueda con soporte para inserción, búsqueda y recorrido.

Estructura e inserción básica

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