--- title: "LinkedList\u003cT\u003e em Rust" url: "https://rustlang.com.br/stdlib/linkedlist/" markdown_url: "https://rustlang.com.br/stdlib/linkedlist.MD" description: "Guia completo do LinkedList em Rust: lista duplamente encadeada, push/pop em ambas as pontas, cursor API, quando usar e por que Vec é geralmente melhor." date: "2026-02-23" author: "Equipe Rust Brasil" --- # LinkedList em Rust Guia completo do LinkedList em Rust: lista duplamente encadeada, push/pop em ambas as pontas, cursor API, quando usar e por que Vec é geralmente melhor. O `LinkedList` é a implementação de **lista duplamente encadeada** da biblioteca padrão do Rust. Cada elemento é armazenado em um nó separado no heap, com ponteiros para o nó anterior e o próximo. Isso permite inserção e remoção em O(1) nas extremidades, mas com acesso por índice em O(n) e localidade de cache deficiente. ## Quando Usar LinkedList (Raramente!) A documentação oficial do Rust é clara: **na maioria dos casos, `Vec` ou `VecDeque` são escolhas melhores**. O `LinkedList` só é vantajoso em cenários muito específicos: - Quando você precisa **dividir** e **concatenar** listas em O(1). - Quando precisa **inserir/remover no meio** da lista com frequência, já tendo uma referência ao nó (via cursor). - Quando o tamanho dos elementos é muito grande e mover dados seria custoso. - Quando precisa de **estabilidade de ponteiros** — os endereços dos elementos não mudam após inserção. Para a grande maioria dos casos, use [`Vec`](/stdlib/vec/) ou [`VecDeque`](/stdlib/vecdeque/). ## Por Que Vec é Geralmente Melhor ``` Vec: [A][B][C][D][E] <- memória contígua, cache-friendly LinkedList: [A]→[B]→[C]→[D]→[E] <- nós espalhados no heap ← ← ← ← ``` | Aspecto | Vec | LinkedList | |---|---|---| | Localidade de cache | Excelente | Ruim | | Overhead por elemento | 0 bytes | ~16 bytes (2 ponteiros) | | Alocações | 1 (buffer contíguo) | N (uma por nó) | | Acesso por índice | O(1) | O(n) | | Push/Pop final | O(1) amortizado | O(1) | | Push/Pop início | O(n) | O(1) | | Iteração | Muito rápida | Lenta (cache misses) | Na prática, mesmo operações que são O(n) no `Vec` (como `insert(0, ...)`) são mais rápidas que as equivalentes O(1) do `LinkedList` para coleções pequenas e médias, devido à localidade de cache. ## Criando e Inicializando ```rust use std::collections::LinkedList; fn main() { // Criar vazia let mut lista: LinkedList = LinkedList::new(); // Criar a partir de um array let numeros = LinkedList::from([1, 2, 3, 4, 5]); // Criar a partir de um iterador let letras: LinkedList = "abcde".chars().collect(); println!("Números: {:?}", numeros); println!("Letras: {:?}", letras); } ``` ## Tabela de Métodos Comuns | Método | Descrição | Complexidade | |---|---|---| | `push_back(value)` | Insere no final | O(1) | | `push_front(value)` | Insere no início | O(1) | | `pop_back()` | Remove do final; retorna `Option` | O(1) | | `pop_front()` | Remove do início; retorna `Option` | O(1) | | `front()` / `back()` | Referência ao primeiro/último | O(1) | | `len()` / `is_empty()` | Tamanho e verificação | O(1) | | `append(&mut other)` | Move todos os elementos de `other` para o final | O(1) | | `clear()` | Remove todos os elementos | O(n) | | `contains(&value)` | Verifica se contém o valor | O(n) | | `iter()` / `iter_mut()` | Iteradores | O(n) | | `split_off(index)` | Divide a lista na posição | O(min(i, n-i)) | | `cursor_front()` | Cursor na frente (imutável) | O(1) | | `cursor_front_mut()` | Cursor na frente (mutável) | O(1) | | `cursor_back()` | Cursor no final (imutável) | O(1) | | `cursor_back_mut()` | Cursor no final (mutável) | O(1) | ## Exemplos Práticos ### 1. Operações Básicas — Push e Pop ```rust use std::collections::LinkedList; fn main() { let mut lista: LinkedList = LinkedList::new(); // Inserir em ambas as pontas lista.push_back("Meio".to_string()); lista.push_front("Início".to_string()); lista.push_back("Fim".to_string()); println!("Lista: {:?}", lista); // ["Início", "Meio", "Fim"] // Acessar primeiro e último println!("Primeiro: {:?}", lista.front()); // Some("Início") println!("Último: {:?}", lista.back()); // Some("Fim") // Remover de ambas as pontas let primeiro = lista.pop_front(); println!("Removido da frente: {:?}", primeiro); // Some("Início") let ultimo = lista.pop_back(); println!("Removido do final: {:?}", ultimo); // Some("Fim") println!("Restante: {:?}", lista); // ["Meio"] println!("Tamanho: {}", lista.len()); // 1 } ``` ### 2. Concatenando e Dividindo Listas — O Ponto Forte ```rust use std::collections::LinkedList; fn main() { let mut lista_a: LinkedList = LinkedList::from([1, 2, 3]); let mut lista_b: LinkedList = LinkedList::from([4, 5, 6]); let mut lista_c: LinkedList = LinkedList::from([7, 8, 9]); // append move todos os elementos de lista_b para lista_a em O(1)! lista_a.append(&mut lista_b); println!("Após append: {:?}", lista_a); // [1, 2, 3, 4, 5, 6] println!("lista_b agora: {:?}", lista_b); // [] (vazia) lista_a.append(&mut lista_c); println!("Após segundo append: {:?}", lista_a); // [1, 2, 3, 4, 5, 6, 7, 8, 9] // split_off divide a lista na posição especificada let segunda_metade = lista_a.split_off(5); println!("Primeira metade: {:?}", lista_a); // [1, 2, 3, 4, 5] println!("Segunda metade: {:?}", segunda_metade); // [6, 7, 8, 9] } ``` ### 3. Iteração e Transformação ```rust use std::collections::LinkedList; fn main() { let numeros: LinkedList = (1..=10).collect(); // Iteração com referências let soma: i32 = numeros.iter().sum(); println!("Soma: {}", soma); // 55 // Filtrar para nova lista let pares: LinkedList = numeros .iter() .filter(|&&n| n % 2 == 0) .copied() .collect(); println!("Pares: {:?}", pares); // [2, 4, 6, 8, 10] // Transformar com map let dobrados: LinkedList = numeros .iter() .map(|&n| n * 2) .collect(); println!("Dobrados: {:?}", dobrados); // Iteração mutável let mut notas: LinkedList = LinkedList::from([7.5, 8.0, 6.5, 9.0]); for nota in notas.iter_mut() { *nota = (*nota * 1.1).min(10.0); // bônus de 10%, máximo 10 } println!("Notas com bônus: {:?}", notas); } ``` ### 4. Cursor API — Navegação e Inserção no Meio ```rust use std::collections::LinkedList; fn main() { let mut lista: LinkedList = LinkedList::from([1, 2, 3, 4, 5]); // Cursor mutável para navegação let mut cursor = lista.cursor_front_mut(); // Avançar até o terceiro elemento cursor.move_next(); // aponta para 1 cursor.move_next(); // aponta para 2 cursor.move_next(); // aponta para 3 // Ler o elemento atual if let Some(valor) = cursor.current() { println!("Elemento atual: {}", valor); // 3 } // Inserir antes e depois do cursor cursor.insert_before(25); // insere 25 antes do 3 cursor.insert_after(35); // insere 35 depois do 3 // Voltar ao início para ver o resultado drop(cursor); println!("Lista após inserções: {:?}", lista); // [1, 2, 25, 3, 35, 4, 5] // Remover com cursor let mut cursor = lista.cursor_front_mut(); cursor.move_next(); // aponta para 1 cursor.move_next(); // aponta para 2 let removido = cursor.remove_current(); // remove o 2 println!("Removido: {:?}", removido); // Some(2) println!("Lista final: {:?}", lista); // [1, 25, 3, 35, 4, 5] } ``` ### 5. Usando como Fila de Tarefas ```rust use std::collections::LinkedList; #[derive(Debug)] struct Tarefa { id: u32, descricao: String, prioridade: u8, } fn main() { let mut fila: LinkedList = LinkedList::new(); // Adicionar tarefas normais no final fila.push_back(Tarefa { id: 1, descricao: "Revisar código".to_string(), prioridade: 2, }); fila.push_back(Tarefa { id: 2, descricao: "Escrever testes".to_string(), prioridade: 2, }); // Tarefa urgente vai para o início fila.push_front(Tarefa { id: 3, descricao: "Corrigir bug em produção".to_string(), prioridade: 1, }); // Processar tarefas em ordem println!("Processando tarefas:"); while let Some(tarefa) = fila.pop_front() { println!( " [P{}] #{}: {}", tarefa.prioridade, tarefa.id, tarefa.descricao ); } // Saída: // [P1] #3: Corrigir bug em produção // [P2] #1: Revisar código // [P2] #2: Escrever testes } ``` ## Características de Desempenho | Operação | LinkedList | Vec | VecDeque | |---|---|---|---| | `push_front` | O(1) | O(n) | O(1) amort. | | `push_back` | O(1) | O(1) amort. | O(1) amort. | | `pop_front` | O(1) | O(n) | O(1) | | `pop_back` | O(1) | O(1) | O(1) | | Acesso por índice | O(n) | O(1) | O(1) | | `append` (concatenar) | **O(1)** | O(m) | O(m) | | `split_off` | O(n) | O(n) | O(n) | | Iteração (real) | Lenta | Rápida | Rápida | | Memória por elemento | ~24 bytes extra | 0 bytes extra | 0 bytes extra | | Alocações | N (uma/nó) | 1 | 1 | **O grande problema:** Apesar das complexidades teóricas favoráveis para certas operações, o `LinkedList` sofre com: - **Cache misses:** Cada nó está em um local diferente do heap, causando falhas de cache na CPU. - **Overhead de alocação:** Cada `push` requer uma alocação no heap (chamada ao alocador). - **Overhead de memória:** Cada nó armazena dois ponteiros adicionais (prev/next), totalizando ~16-24 bytes extras por elemento. ## Quando LinkedList Realmente Vale a Pena 1. **Concatenação frequente de listas:** Se você concatena listas inteiras com `append` muitas vezes, o O(1) do `LinkedList` supera o O(m) do `Vec`. 2. **Estabilidade de referências:** Os endereços dos elementos nunca mudam, ao contrário do `Vec` que pode realocar. 3. **Inserção/remoção no meio com cursor:** Se você navega com cursores e insere/remove frequentemente no meio, sem precisar de acesso por índice. 4. **Elementos muito grandes:** Se cada elemento ocupa muita memória (ex.: structs de KBs), mover dados no `Vec` seria caro. Para todos os outros casos, `Vec` ou `VecDeque` serão mais rápidos na prática. ## Veja Também - [Vec em Rust](/stdlib/vec/) --- vetor dinâmico, quase sempre a melhor escolha - [VecDeque: Fila de Duas Pontas](/stdlib/vecdeque/) --- alternativa superior na maioria dos casos - [BinaryHeap: Fila de Prioridade](/stdlib/binaryheap/) --- quando precisa processar por prioridade - [Variáveis, Tipos e Funções](/tutoriais/variaveis-tipos-funcoes/) --- fundamentos dos tipos - [Traits e Generics](/tutoriais/traits-generics/) --- entendendo iteradores e traits