--- title: "Listas Ligadas em Rust: Desafios e Implementações" url: "https://rustlang.com.br/estruturas-dados/lista-ligada/" markdown_url: "https://rustlang.com.br/estruturas-dados/lista-ligada.MD" description: "Guia completo sobre listas ligadas em Rust — por que são difíceis, implementação com Box, considerações sobre listas duplamente ligadas e quando usar std::collections::LinkedList." date: "" author: "Equipe Rust Brasil" --- # Listas Ligadas em Rust: Desafios e Implementações Guia completo sobre listas ligadas em Rust — por que são difíceis, implementação com Box, considerações sobre listas duplamente ligadas e quando usar std::collections::LinkedList. ## Introdução Listas ligadas são uma das estruturas de dados mais clássicas da ciência da computação. Em linguagens como C, Java ou Python, implementá-las é quase trivial. Em Rust, porém, essa tarefa se torna um exercício profundo sobre o sistema de ownership, borrowing e lifetimes. A dificuldade não é um defeito — é uma **revelação**. As listas ligadas violam naturalmente muitas garantias que Rust busca oferecer: cada nó precisa apontar para o próximo, criando relações de propriedade complexas. Listas duplamente ligadas introduzem referências cíclicas, que são fundamentalmente incompatíveis com o modelo de ownership simples de Rust. Este artigo é inspirado pelo famoso tutorial "Learn Rust With Entirely Too Many Linked Lists" de Alexis Beresford, uma referência essencial para quem quer entender Rust profundamente. Aqui, abordaremos os conceitos teóricos, a implementação prática e, crucialmente, discutiremos quando **não** usar listas ligadas em Rust. --- ## Conceito e Teoria ### Lista Simplesmente Ligada Cada nó contém um valor e um ponteiro para o próximo nó. O último nó aponta para "nada" (None): ``` head │ ▼ ┌────────────┐ ┌────────────┐ ┌────────────┐ ┌────────────┐ │ valor: 10 │ │ valor: 20 │ │ valor: 30 │ │ valor: 40 │ │ next: ─────┼───►│ next: ─────┼───►│ next: ─────┼───►│ next: None │ └────────────┘ └────────────┘ └────────────┘ └────────────┘ Nó 0 Nó 1 Nó 2 Nó 3 Cada nó está em uma posição DIFERENTE na heap. Não há garantia de que estejam próximos na memória. ``` ### Lista Duplamente Ligada Cada nó possui ponteiros tanto para o próximo quanto para o anterior: ``` head tail │ │ ▼ ▼ ┌──────────────┐ ┌──────────────┐ ┌──────────────┐ ┌──────────────┐ │ prev: None │◄────┤ prev: ───────│◄────┤ prev: ───────│◄───┤ prev: ───────│ │ valor: 10 │ │ valor: 20 │ │ valor: 30 │ │ valor: 40 │ │ next: ───────┼────►│ next: ───────┼────►│ next: ───────┼───►│ next: None │ └──────────────┘ └──────────────┘ └──────────────┘ └──────────────┘ ``` ### Layout de Memória: Vec vs Lista Ligada ``` Vec — memória contígua (excelente para cache): ┌────┬────┬────┬────┬────┐ │ 10 │ 20 │ 30 │ 40 │ 50 │ ← tudo junto na heap └────┴────┴────┴────┴────┘ Endereços: 0x1000, 0x1004, 0x1008, 0x100C, 0x1010 LinkedList — nós espalhados na heap: 0x2000: [10, ptr] ──► 0x3050: [20, ptr] ──► 0x2F00: [30, ptr] ──► ... │ │ │ Cada acesso ao Os endereços podem Cache misses frequentes! próximo nó pode estar muito distantes causar cache miss ``` ### Por Que Listas Ligadas São Difíceis em Rust? O sistema de ownership do Rust impõe regras que entram em conflito com a natureza das listas: 1. **Cada valor tem exatamente um dono**: Em uma lista simplesmente ligada, cada nó "possui" o próximo. Isso funciona com `Box`. Mas quem possui a lista inteira? 2. **Referências cíclicas são proibidas**: Uma lista duplamente ligada cria ciclos: A aponta para B, que aponta de volta para A. Isso é impossível com referências simples. 3. **Mutabilidade compartilhada**: Para inserir no meio da lista, você precisa de acesso mutável a um nó enquanto outro nó ainda referencia a lista. --- ## Complexidade | Operação | Lista Simples | Lista Dupla | Vec | |---------------------------------|---------------|-------------|-----------------| | Acesso por índice | O(n) | O(n) | O(1) | | Busca | O(n) | O(n) | O(n) | | Inserção no início | O(1) | O(1) | O(n) | | Inserção no final (com tail) | O(1) | O(1) | O(1) amortizado | | Inserção no meio (com ponteiro) | O(1) | O(1) | O(n) | | Remoção no início | O(1) | O(1) | O(n) | | Remoção no final | O(n) | O(1) | O(1) | | Remoção no meio (com ponteiro) | O(1)* | O(1) | O(n) | | Uso de memória por elemento | Alto | Muito alto | Baixo | > *Na lista simples, remover um nó requer acesso ao nó **anterior**, o que pode custar O(n) > se não tivermos esse ponteiro. --- ## Implementação em Rust ### Lista Simplesmente Ligada com Box Esta é a implementação mais idiomática e segura em Rust: ```rust use std::fmt; /// Tipo auxiliar para o ponteiro para o próximo nó type Link = Option>>; /// Nó da lista ligada #[derive(Debug)] struct No { valor: T, proximo: Link, } /// Lista simplesmente ligada #[derive(Debug)] pub struct ListaLigada { cabeca: Link, tamanho: usize, } impl ListaLigada { /// Cria uma lista vazia pub fn nova() -> Self { ListaLigada { cabeca: None, tamanho: 0, } } /// Retorna o número de elementos na lista pub fn tamanho(&self) -> usize { self.tamanho } /// Verifica se a lista está vazia pub fn esta_vazia(&self) -> bool { self.tamanho == 0 } /// Insere um elemento no início da lista — O(1) pub fn inserir_inicio(&mut self, valor: T) { let novo_no = Box::new(No { valor, // O novo nó assume a propriedade (ownership) da cabeça anterior proximo: self.cabeca.take(), }); self.cabeca = Some(novo_no); self.tamanho += 1; } /// Remove e retorna o elemento do início da lista — O(1) pub fn remover_inicio(&mut self) -> Option { // take() substitui self.cabeca por None e retorna o valor anterior self.cabeca.take().map(|no| { self.cabeca = no.proximo; self.tamanho -= 1; no.valor }) } /// Retorna uma referência ao primeiro elemento — O(1) pub fn espiar(&self) -> Option<&T> { self.cabeca.as_ref().map(|no| &no.valor) } /// Retorna uma referência mutável ao primeiro elemento — O(1) pub fn espiar_mut(&mut self) -> Option<&mut T> { self.cabeca.as_mut().map(|no| &mut no.valor) } /// Insere um elemento no final da lista — O(n) pub fn inserir_final(&mut self, valor: T) { let novo_no = Box::new(No { valor, proximo: None, }); // Caso especial: lista vazia if self.cabeca.is_none() { self.cabeca = Some(novo_no); self.tamanho += 1; return; } // Percorre até o último nó let mut atual = &mut self.cabeca; while let Some(ref mut no) = atual { if no.proximo.is_none() { no.proximo = Some(novo_no); self.tamanho += 1; return; } atual = &mut no.proximo; } } /// Verifica se a lista contém um determinado valor — O(n) pub fn contem(&self, alvo: &T) -> bool where T: PartialEq, { let mut atual = &self.cabeca; while let Some(ref no) = atual { if &no.valor == alvo { return true; } atual = &no.proximo; } false } /// Converte a lista em um Vec — O(n) pub fn para_vec(&self) -> Vec<&T> { let mut resultado = Vec::with_capacity(self.tamanho); let mut atual = &self.cabeca; while let Some(ref no) = atual { resultado.push(&no.valor); atual = &no.proximo; } resultado } } /// Implementação do iterador para consumir a lista impl Iterator for ListaLigada { type Item = T; fn next(&mut self) -> Option { self.remover_inicio() } } /// Implementação do Display para visualização impl fmt::Display for ListaLigada { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { let mut atual = &self.cabeca; write!(f, "[")?; let mut primeiro = true; while let Some(ref no) = atual { if !primeiro { write!(f, " → ")?; } write!(f, "{}", no.valor)?; primeiro = false; atual = &no.proximo; } write!(f, "]") } } /// Libera a memória iterativamente para evitar estouro de pilha /// em listas muito grandes (o Drop padrão seria recursivo) impl Drop for ListaLigada { fn drop(&mut self) { let mut link_atual = self.cabeca.take(); while let Some(mut no) = link_atual { link_atual = no.proximo.take(); // 'no' é descartado aqui sem recursão } } } fn main() { let mut lista = ListaLigada::nova(); // Inserções no início lista.inserir_inicio(30); lista.inserir_inicio(20); lista.inserir_inicio(10); println!("Após inserções no início: {}", lista); // Inserção no final lista.inserir_final(40); lista.inserir_final(50); println!("Após inserções no final: {}", lista); // Espiar o primeiro elemento if let Some(primeiro) = lista.espiar() { println!("Primeiro elemento: {}", primeiro); } // Remover do início let removido = lista.remover_inicio(); println!("Removido: {:?}", removido); println!("Lista após remoção: {}", lista); // Verificar se contém println!("Contém 30? {}", lista.contem(&30)); println!("Contém 99? {}", lista.contem(&99)); // Tamanho println!("Tamanho: {}", lista.tamanho()); // Converter para Vec println!("Como Vec: {:?}", lista.para_vec()); } ``` ### Iterador por Referência (Sem Consumir a Lista) ```rust /// Iterador que empresta elementos da lista (não consome) pub struct Iter<'a, T> { proximo: Option<&'a No>, } impl ListaLigada { /// Retorna um iterador por referência imutável pub fn iter(&self) -> Iter<'_, T> { Iter { proximo: self.cabeca.as_deref(), } } } impl<'a, T> Iterator for Iter<'a, T> { type Item = &'a T; fn next(&mut self) -> Option { self.proximo.map(|no| { self.proximo = no.proximo.as_deref(); &no.valor }) } } // Uso: // for valor in lista.iter() { // println!("{}", valor); // } ``` --- ## Métodos Principais ### Nossa Implementação | Método | Complexidade | Descrição | |---------------------|--------------|-----------------------------------------------------| | `nova()` | O(1) | Cria uma lista vazia | | `inserir_inicio(v)` | O(1) | Adiciona no início | | `remover_inicio()` | O(1) | Remove e retorna o primeiro elemento | | `inserir_final(v)` | O(n) | Adiciona no final (sem ponteiro tail) | | `espiar()` | O(1) | Referência ao primeiro elemento | | `contem(v)` | O(n) | Busca linear | | `para_vec()` | O(n) | Converte para vetor de referências | | `tamanho()` | O(1) | Retorna o número de elementos | | `esta_vazia()` | O(1) | Verifica se está vazia | | `iter()` | O(1) | Cria iterador por referência | ### std::collections::LinkedList A biblioteca padrão oferece uma lista duplamente ligada: | Método | Complexidade | Descrição | |---------------------|--------------|---------------------------------------| | `push_front(v)` | O(1) | Insere no início | | `push_back(v)` | O(1) | Insere no final | | `pop_front()` | O(1) | Remove do início | | `pop_back()` | O(1) | Remove do final | | `front()` / `back()` | O(1) | Referência ao primeiro/último | | `len()` | O(1) | Número de elementos | | `contains(v)` | O(n) | Busca linear | | `iter()` | O(1) | Cria iterador | --- ## Exemplo Prático: Sistema de Histórico de Desfazer (Undo) Um caso de uso clássico de listas ligadas é implementar um sistema de undo/redo. Cada ação é empilhada na lista, e desfazer remove a ação mais recente. ```rust use std::fmt; type Link = Option>>; struct No { valor: T, proximo: Link, } struct Pilha { topo: Link, tamanho: usize, } impl Pilha { fn nova() -> Self { Pilha { topo: None, tamanho: 0 } } fn empilhar(&mut self, valor: T) { let novo = Box::new(No { valor, proximo: self.topo.take(), }); self.topo = Some(novo); self.tamanho += 1; } fn desempilhar(&mut self) -> Option { self.topo.take().map(|no| { self.topo = no.proximo; self.tamanho -= 1; no.valor }) } fn espiar(&self) -> Option<&T> { self.topo.as_ref().map(|no| &no.valor) } fn esta_vazia(&self) -> bool { self.tamanho == 0 } } /// Representa uma ação que pode ser desfeita #[derive(Debug, Clone)] enum Acao { InserirTexto { posicao: usize, texto: String }, RemoverTexto { posicao: usize, texto: String }, FormatarNegrito { inicio: usize, fim: usize }, FormatarItalico { inicio: usize, fim: usize }, SubstituirTexto { posicao: usize, antigo: String, novo: String }, } impl fmt::Display for Acao { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { match self { Acao::InserirTexto { posicao, texto } => { write!(f, "Inserir '{}' na posição {}", texto, posicao) } Acao::RemoverTexto { posicao, texto } => { write!(f, "Remover '{}' da posição {}", texto, posicao) } Acao::FormatarNegrito { inicio, fim } => { write!(f, "Negrito em [{}, {})", inicio, fim) } Acao::FormatarItalico { inicio, fim } => { write!(f, "Itálico em [{}, {})", inicio, fim) } Acao::SubstituirTexto { posicao, antigo, novo } => { write!(f, "Substituir '{}' por '{}' na posição {}", antigo, novo, posicao) } } } } /// Inverte uma ação para gerar a ação de desfazer fn inverter_acao(acao: &Acao) -> Acao { match acao { Acao::InserirTexto { posicao, texto } => Acao::RemoverTexto { posicao: *posicao, texto: texto.clone(), }, Acao::RemoverTexto { posicao, texto } => Acao::InserirTexto { posicao: *posicao, texto: texto.clone(), }, Acao::FormatarNegrito { inicio, fim } => Acao::FormatarNegrito { inicio: *inicio, fim: *fim, }, Acao::FormatarItalico { inicio, fim } => Acao::FormatarItalico { inicio: *inicio, fim: *fim, }, Acao::SubstituirTexto { posicao, antigo, novo } => Acao::SubstituirTexto { posicao: *posicao, antigo: novo.clone(), novo: antigo.clone(), }, } } /// Sistema de histórico com undo e redo struct HistoricoEditor { historico_desfazer: Pilha, historico_refazer: Pilha, } impl HistoricoEditor { fn novo() -> Self { HistoricoEditor { historico_desfazer: Pilha::nova(), historico_refazer: Pilha::nova(), } } /// Registra uma nova ação (limpa o histórico de refazer) fn executar(&mut self, acao: Acao) { println!(" ✔ Executando: {}", acao); self.historico_desfazer.empilhar(acao); // Ao executar nova ação, o histórico de refazer é invalidado self.historico_refazer = Pilha::nova(); } /// Desfaz a última ação fn desfazer(&mut self) -> Option { self.historico_desfazer.desempilhar().map(|acao| { let acao_inversa = inverter_acao(&acao); println!(" ↩ Desfazendo: {} → Aplicando: {}", acao, acao_inversa); self.historico_refazer.empilhar(acao.clone()); acao_inversa }) } /// Refaz a última ação desfeita fn refazer(&mut self) -> Option { self.historico_refazer.desempilhar().map(|acao| { println!(" ↪ Refazendo: {}", acao); self.historico_desfazer.empilhar(acao.clone()); acao }) } /// Mostra o estado atual fn estado(&self) { print!(" Estado: "); if let Some(ultima) = self.historico_desfazer.espiar() { println!("última ação = {}", ultima); } else { println!("nenhuma ação no histórico"); } } } fn main() { let mut editor = HistoricoEditor::novo(); println!("═══ Simulação de Editor de Texto ═══\n"); // Usuário digita e formata texto println!("── Executando ações ──"); editor.executar(Acao::InserirTexto { posicao: 0, texto: "Olá, ".to_string(), }); editor.executar(Acao::InserirTexto { posicao: 5, texto: "mundo!".to_string(), }); editor.executar(Acao::FormatarNegrito { inicio: 0, fim: 3 }); editor.executar(Acao::SubstituirTexto { posicao: 5, antigo: "mundo".to_string(), novo: "Rust".to_string(), }); editor.estado(); // Desfazer duas vezes println!("\n── Desfazendo ──"); editor.desfazer(); editor.desfazer(); editor.estado(); // Refazer uma vez println!("\n── Refazendo ──"); editor.refazer(); editor.estado(); // Nova ação após desfazer (invalida o refazer) println!("\n── Nova ação (invalida refazer) ──"); editor.executar(Acao::FormatarItalico { inicio: 0, fim: 11 }); // Tentar refazer (não deve funcionar) println!("\n── Tentando refazer ──"); match editor.refazer() { Some(acao) => println!(" Refez: {}", acao), None => println!(" Nada para refazer (histórico foi invalidado)"), } } ``` --- ## Comparação com Outras Estruturas | Critério | Lista Ligada (Box) | Vec | VecDeque | |------------------------------|----------------------|-------------------|--------------------| | Inserção início | O(1) | O(n) | O(1) amortizado | | Inserção final | O(n) ou O(1)* | O(1) amortizado | O(1) amortizado | | Acesso aleatório | O(n) | O(1) | O(1) | | Cache-friendly | Nao | Sim | Sim | | Overhead por elemento | ~8-16 bytes (ptr) | 0 | 0 | | Fragmentação de memória | Alta | Nenhuma | Nenhuma | | Propriedade (ownership) | Clara (linear) | Clara | Clara | > *O(1) no final se mantivermos um ponteiro `tail`, mas isso complica o ownership em Rust. ### Quando Usar Lista Ligada em Rust? **Raramente.** Na prática, `Vec` ou `VecDeque` são quase sempre superiores devido à localidade de cache. Use listas ligadas quando: 1. **Precisa de inserção/remoção O(1) no início** e não pode usar VecDeque por algum motivo. 2. **Está implementando estruturas mais complexas** como grafos ou árvores internamente. 3. **Fins educacionais** — aprender sobre ownership e lifetimes em Rust. 4. **Precisa dividir e juntar listas frequentemente** — `split_off` e `append` são O(1) em listas ligadas mas O(n) em vetores. 5. **Elementos são muito grandes** e a realocação/cópia de Vec seria custosa. ### O Conselho da Comunidade Rust A comunidade Rust geralmente recomenda: "Se você está pensando em usar uma lista ligada, use um Vec." O próprio `std::collections::LinkedList` inclui um aviso na documentação de que é quase sempre inferior ao `Vec` ou `VecDeque`. --- ## Exercícios ### Exercício 1: Reverter uma Lista Ligada Implemente uma função `reverter(lista: &mut ListaLigada)` que inverte a ordem dos elementos da lista **in-place**, sem alocar uma nova lista. A complexidade deve ser O(n) de tempo e O(1) de espaço adicional. **Dica:** Use três ponteiros (anterior, atual, próximo) e vá redirecionando os links. ### Exercício 2: Detectar Ciclo (Conceitual) Embora nossa implementação com `Box` não permita ciclos (o sistema de ownership impede), descreva o algoritmo de Floyd (tartaruga e lebre) para detecção de ciclos. Implemente uma versão que funcione com índices em um `Vec>` simulando os ponteiros. **Dica:** Use dois "ponteiros" (índices): um avança um passo por vez, outro avança dois. Se se encontrarem, há um ciclo. ### Exercício 3: Merge de Duas Listas Ordenadas Implemente uma função `merge_ordenado(l1: ListaLigada, l2: ListaLigada) -> ListaLigada` que recebe duas listas ordenadas e retorna uma nova lista ordenada contendo todos os elementos de ambas. A complexidade deve ser O(n + m). **Dica:** Consuma ambas as listas usando `remover_inicio()` e compare os valores para decidir qual inserir primeiro na lista resultado. --- ## Conclusão Listas ligadas em Rust são um excelente exercício de aprendizado, mas raramente a melhor escolha para código de produção. As principais lições deste artigo: 1. **O sistema de ownership do Rust expõe problemas reais** que outras linguagens escondem (referências cíclicas, mutabilidade compartilhada). 2. **Listas simplesmente ligadas com `Box`** são seguras e relativamente simples de implementar, mas limitadas (sem acesso eficiente ao final). 3. **Listas duplamente ligadas** requerem `Rc>` ou código `unsafe`, aumentando consideravelmente a complexidade. 4. **Na prática, prefira `Vec` ou `VecDeque`** — a localidade de cache supera as vantagens teóricas de listas ligadas na maioria dos cenários. 5. **Para aprofundamento**, leia "Learn Rust With Entirely Too Many Linked Lists", que explora seis variações de listas ligadas e é uma das melhores formas de dominar conceitos avançados de Rust. A verdadeira sabedoria em estruturas de dados não é saber implementar todas elas, mas saber **quando cada uma é a escolha certa** para o problema em questão.