LinkedList<T> em Rust

O LinkedList<T> é 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 ou 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

use std::collections::LinkedList;

fn main() {
    // Criar vazia
    let mut lista: LinkedList<i32> = 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<char> = "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<T>`	O(1)
`pop_front()`	Remove do início; retorna `Option<T>`	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

use std::collections::LinkedList;

fn main() {
    let mut lista: LinkedList<String> = 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

use std::collections::LinkedList;

fn main() {
    let mut lista_a: LinkedList<i32> = LinkedList::from([1, 2, 3]);
    let mut lista_b: LinkedList<i32> = LinkedList::from([4, 5, 6]);
    let mut lista_c: LinkedList<i32> = 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

use std::collections::LinkedList;

fn main() {
    let numeros: LinkedList<i32> = (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<i32> = numeros
        .iter()
        .filter(|&&n| n % 2 == 0)
        .copied()
        .collect();
    println!("Pares: {:?}", pares); // [2, 4, 6, 8, 10]

    // Transformar com map
    let dobrados: LinkedList<i32> = numeros
        .iter()
        .map(|&n| n * 2)
        .collect();
    println!("Dobrados: {:?}", dobrados);

    // Iteração mutável
    let mut notas: LinkedList<f64> = 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

use std::collections::LinkedList;

fn main() {
    let mut lista: LinkedList<i32> = 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

use std::collections::LinkedList;

#[derive(Debug)]
struct Tarefa {
    id: u32,
    descricao: String,
    prioridade: u8,
}

fn main() {
    let mut fila: LinkedList<Tarefa> = 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

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.
Estabilidade de referências: Os endereços dos elementos nunca mudam, ao contrário do Vec que pode realocar.
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.
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 — vetor dinâmico, quase sempre a melhor escolha
VecDeque: Fila de Duas Pontas — alternativa superior na maioria dos casos
BinaryHeap: Fila de Prioridade — quando precisa processar por prioridade
Variáveis, Tipos e Funções — fundamentos dos tipos
Traits e Generics — entendendo iteradores e traits