Médio Rust

Lista encadeada recursiva

Enunciado

Implemente uma lista encadeada simples usando enum e Box. A lista deve ter um método tamanho que retorna o número de elementos. Crie uma lista com os valores 10, 20 e 30 e imprima o tamanho e o primeiro elemento.

Requisitos

  • Defina um enum Lista com variantes No(i32, Box<Lista>) e Fim.
  • Implemente fn tamanho(&self) -> usize.
  • Implemente fn primeiro(&self) -> Option<i32>.
  • Crie a lista e imprima tamanho e primeiro elemento.

Código inicial

enum Lista {
    No(i32, Box<Lista>),
    Fim,
}

impl Lista {
    // implemente tamanho e primeiro
}

fn main() {
    // crie a lista e imprima
}

Saída esperada

Tamanho: 3
Primeiro: 10
Ver dica

Para tamanho, use recursão: No(_, resto) => 1 + resto.tamanho().

Mostrar solução 
enum Lista {
    No(i32, Box<Lista>),
    Fim,
}

impl Lista {
    // Retorna o número de elementos na lista
    fn tamanho(&self) -> usize {
        match self {
            Lista::No(_, resto) => 1 + resto.tamanho(),
            Lista::Fim => 0,
        }
    }

    // Retorna o primeiro elemento, se existir
    fn primeiro(&self) -> Option<i32> {
        match self {
            Lista::No(valor, _) => Some(*valor),
            Lista::Fim => None,
        }
    }
}

fn main() {
    // Cria a lista: 10 -> 20 -> 30 -> Fim
    let lista = Lista::No(10, Box::new(Lista::No(20, Box::new(Lista::No(30, Box::new(Lista::Fim))))));

    println!("Tamanho: {}", lista.tamanho());
    println!("Primeiro: {}", lista.primeiro().unwrap());
}

Passo a passo

  1. O enum Lista tem uma variante No que contém um i32 e um Box<Lista>. O Box é necessário porque sem ele o tipo teria tamanho infinito (recursão infinita).
  2. tamanho usa match: se for No, soma 1 ao tamanho do resto; se for Fim, retorna 0.
  3. primeiro retorna Some(*valor) para a variante No e None para Fim.
  4. No main, construímos a lista aninhando Box::new.
  5. unwrap() é seguro porque a lista não está vazia.

Por que funciona

O Box quebra a recursão de tamanho: em vez de armazenar outro Lista diretamente (o que seria infinito), armazena um ponteiro de tamanho fixo. Assim, o compilador sabe o tamanho de Lista. A recursão em tamanho percorre a lista até Fim.

Erros comuns

  • Esquecer o Box: No(i32, Lista) não compila porque o tamanho seria infinito.
  • Não desreferenciar em primeiro: Some(valor) em vez de Some(*valor) dá erro de tipo.
  • Usar unwrap em lista vazia: causaria panic; o correto é tratar None.

Outra forma de resolver

Usar Option<Box<Lista>> em vez de um enum com Fim, mas a solução com enum é mais explícita.

Saída esperada

Tamanho: 3
Primeiro: 10