Algoritmos e Estruturas de Dados em Rust: Guia Prático

Introdução: Por que Rust para algoritmos?

Rust é uma linguagem moderna de programação de sistemas que combina o alto desempenho de C/C++ com segurança de memória. Para estudar algoritmos e estruturas de dados, Rust é especialmente bom porque:

• Controle de propriedade (ownership) força você a pensar explicitamente sobre o gerenciamento de memória
• Segurança — o compilador não permite muitos erros de tempo de execução
• Velocidade — Rust compila para código de máquina, o que é importante para algoritmos de alto desempenho

Neste artigo, vamos analisar a implementação de quatro estruturas e algoritmos básicos em Rust com exemplos práticos de código.

1. Lista Encadeada (Linked List)

Uma das estruturas de dados clássicas. Em Rust, sua implementação requer o uso de Box para alocar memória no heap e Option para representar a ausência de um nó.

Implementação de uma lista simplesmente encadeada

// Definindo o nó da lista#[derive(Debug)]struct Node<T> {    value: T,    next: Option<Box<Node<T>>>,}

// A lista em si#[derive(Debug)]struct LinkedList<T> {    head: Option<Box<Node<T>>>,}

impl<T> LinkedList<T> {    // Criando uma lista vazia    fn new() -> Self {        LinkedList { head: None }    }

    // Adicionando um elemento no início    fn push_front(&mut self, value: T) {        let new_node = Box::new(Node {            value,            next: self.head.take(),        });        self.head = Some(new_node);    }

    // Removendo um elemento do início    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!("Removido: {:?}", popped); // Removido: Some(30)    println!("Agora a lista: {:?}", list);}

O que está acontecendo aqui:

• Box<Node> — ponteiro para um nó no heap
• Option — ou há um nó (Some) ou não (None)
• take() — pega o valor de Option, deixando None

2. Árvore Binária de Busca (Binary Search Tree)

Uma árvore é uma estrutura hierárquica. Em uma árvore binária de busca, cada nó tem um filho esquerdo e um direito, onde o esquerdo é menor que a raiz e o direito é maior.

Implementação de 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 }    }

    // Inserção de elemento    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, // duplicatas são ignoradas            }        }        *current = Some(Box::new(TreeNode {            value,            left: None,            right: None,        }));    }

    // Busca de elemento    fn contains(&self, value: &T) -> bool {        let mut current = &self.root;        while let