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

Introdução a Algoritmos e Estruturas de Dados em Rust

A linguagem de programação Rust conquistou o reconhecimento dos desenvolvedores devido ao seu alto desempenho e rigorosas garantias de segurança de memória. No entanto, a transição para Rust a partir de outras linguagens, como Python ou JavaScript, pode ser desafiadora, especialmente ao implementar algoritmos e estruturas de dados clássicos. Neste artigo, veremos como implementar eficientemente estruturas de dados básicas e algoritmos em Rust, levando em consideração as particularidades do sistema de ownership e borrowing.

O artigo é destinado a desenvolvedores que já conhecem os fundamentos do Rust. Vamos nos concentrar em exemplos práticos de código que podem ser usados imediatamente em projetos reais. Todos os exemplos serão acompanhados de comentários detalhados.

Implementação de uma Lista Encadeada em Rust

A lista encadeada é uma das estruturas de dados fundamentais. Em Rust, sua implementação requer atenção especial devido às regras de ownership. Vamos considerar uma lista simplesmente encadeada usando Box para gerenciamento de memória.

Lista Simplesmente Encadeada Básica

Vamos começar definindo o nó e a própria 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    }}

Observe o uso de Option<Box<Node<T>>>. Esta é a forma padrão de criar estruturas recursivas em Rust, pois o compilador exige um tamanho conhecido antecipadamente. O método take() permite extrair com segurança o valor de Option, substituindo-o por None.

Iteração pela Lista

Vamos implementar um iterador para a 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        })    }}

Árvore Binária de Busca (BST) em Rust

Árvores são outra estrutura importante. Vamos implementar uma árvore binária de busca com suporte para inserção, busca e travessia.

Estrutura e Inserção 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 < 
```