8 - Implementando una lista enlazada en Rust - parte 1

8 - Implementando una lista enlazada en Rust - parte 1

¡Bienvenidos de nuevo a Rustaceo.es! En nuestra búsqueda por profundizar en Rust y entender sus conceptos más avanzados, hoy comenzaremos a implementar una lista enlazada desde cero. Como siempre, usaremos ejemplos del mundo Pokémon para hacer este viaje más entretenido y comprensible. Esta es la primera parte de una serie donde exploraremos cómo construir estructuras de datos en Rust, enfrentando desafíos relacionados con la propiedad, los préstamos y los tiempos de vida.

¿Por qué una lista enlazada? #

Las listas enlazadas son una estructura de datos fundamental que consiste en una serie de nodos, donde cada nodo contiene un valor y una referencia al siguiente nodo. Aunque Rust proporciona colecciones como Vec y LinkedList en su biblioteca estándar, implementar una lista enlazada nosotros mismos nos ayudará a entender mejor cómo Rust maneja la memoria y las referencias.

Objetivos de esta parte #

  • Definir la estructura básica de una lista enlazada sencilla.
  • Entender cómo manejar referencias y propiedad en estructuras recursivas.
  • Implementar métodos básicos como inserción al frente de la lista.

Conceptos clave a explorar #

  • Enumeraciones (enum) y Opciones (Option).
  • Tipos de Datos Recursivos.
  • Propiedad y Referencias en Estructuras Autorreferenciales.

Definiendo nuestra lista enlazada de pokémon #

Empecemos por definir una estructura para nuestro nodo. Cada nodo contendrá un Pokémon y una referencia al siguiente nodo.

Paso 1: definir el nodo # 

#[Derive(debug)]
struct Pokémon {
    nombre: String,
    tipo: String,
    nivel: u8,
}

Creamos una estructura Pokémon que representa a un Pokémon con su nombre, tipo y nivel.

Ahora, definamos el nodo de la lista enlazada:

type Link = Option<Box<Nodo>>;

struct Nodo {
    pokemon: Pokémon,
    siguiente: Link,
}

Aquí:

  • Link es un tipo alias para Option<Box<Nodo>>. Usamos Box para crear un puntero en el montón (stack) a otro nodo.
  • Nodo contiene un Pokémon y un enlace (siguiente) al siguiente nodo.

Por qué usamos option y box #

  • Option: Necesitamos poder representar el final de la lista, lo cual hacemos usando None.
  • Box: En Rust, las estructuras no pueden contenerse a sí mismas directamente debido a que el compilador necesita conocer el tamaño de cada estructura en tiempo de compilación. Usando Box, podemos almacenar el nodo en el montón y manejar un puntero a él, lo que nos permite crear estructuras recursivas.

Paso 2: definir la lista # 

pub struct ListaEnlazada {
    cabeza: Link,
}

Nuestra ListaEnlazada tendrá una referencia a la cabeza de la lista.

Implementando funciones básicas #

Creación de una lista vacía #

Comencemos implementando un método para crear una lista vacía.

impl ListaEnlazada {
    pub fn nueva() -> Self {
        ListaEnlazada { cabeza: None }
    }
}

Insertar un pokémon al frente de la lista #

Ahora, implementemos un método para insertar un Pokémon al frente de la lista.

impl ListaEnlazada {
    // ... código anterior ...

    pub fn insertar_al_frente(&mut self, pokemon: Pokémon) {
        let nuevo_nodo = Nodo {
            pokemon: pokemon,
            siguiente: self.cabeza.take(),
        };
        self.cabeza = Some(Box::new(nuevo_nodo));
    }
}

Explicación:

  • self.cabeza.take(): take() reemplaza self.cabeza con None y retorna el valor original. Esto nos permite mover la antigua cabeza de la lista al campo siguiente del nuevo nodo.
  • Creamos un nuevo_nodo con el pokemon proporcionado y el enlace al siguiente nodo.
  • Actualizamos self.cabeza para que apunte al nuevo_nodo.

Visualizando la lista #

Para verificar que nuestra lista está funcionando, implementemos un método para imprimir los Pokémon en la lista.

impl ListaEnlazada {
    // ... código anterior ...

    pub fn imprimir_lista(&self) {
        let mut actual = &self.cabeza;
        while let Some(nodo) = actual {
            println!(
                "{} - Tipo: {}, Nivel: {}",
                nodo.pokemon.nombre, nodo.pokemon.tipo, nodo.pokemon.nivel
            );
            actual = &nodo.siguiente;
        }
    }
}

Probando nuestra lista enlazada #

Es hora de poner todo junto y probar nuestra lista enlazada.

fn main() {
    let mut lista = ListaEnlazada::nueva();

    let item1 = Pokémon {
        nombre: String::from("Item1"),
        tipo: String::from("Eléctrico"),
        nivel: 25,
    };

    let item4 = Pokémon {
        nombre: String::from("Item4"),
        tipo: String::from("Planta/Veneno"),
        nivel: 15,
    };

    let item2 = Pokémon {
        nombre: String::from("Item2"),
        tipo: String::from("Fuego"),
        nivel: 12,
    };

    lista.insertar_al_frente(item1);
    lista.insertar_al_frente(item4);
    lista.insertar_al_frente(item2);

    println!("Equipo Pokémon en la lista enlazada:");
    lista.imprimir_lista();
}

Resultado esperado #

Al ejecutar el programa, deberíamos ver:

Equipo Pokémon en la lista enlazada:
Item2 - Tipo: Fuego, Nivel: 12
Item4 - Tipo: Planta/Veneno, Nivel: 15
Item1 - Tipo: Eléctrico, Nivel: 25

Esto confirma que los Pokémon se insertan al frente de la lista, siendo Item2 el primero.

Entendiendo los desafíos de la propiedad #

El uso de box #

Sin Box, intentaríamos definir Nodo de la siguiente manera:

struct Nodo {
    pokemon: Pokémon,
    siguiente: Option<Nodo>,
}

Esto generaría un error:

error[E0072]: recursive type `Nodo` has infinite size

El compilador no puede calcular el tamaño de Nodo porque cada Nodo contendría otro Nodo infinitamente. Usando Box, creamos una referencia en el montón, y el tamaño del puntero es conocido.

Manipulación de option #

Al trabajar con Option, debemos manejar los casos de Some y None. Usamos patrones como while let para iterar sobre la lista.

Implementando el método pop #

Agreguemos un método para eliminar y retornar el primer Pokémon de la lista.

impl ListaEnlazada {
    // ... código anterior ...

    pub fn pop(&mut self) -> Option<Pokémon> {
        self.cabeza.take().map(|nodo| {
            self.cabeza = nodo.siguiente;
            nodo.pokemon
        })
    }
}

Explicación:

  • self.cabeza.take(): Reemplaza self.cabeza con None y nos da el Some(nodo) original.
  • Usamos map para aplicar una función si self.cabeza es Some.
  • Actualizamos self.cabeza para que apunte al siguiente nodo.
  • Retornamos el pokemon del nodo eliminado.

Probando el método pop #

Agreguemos lo siguiente en main:

if let Some(pokemon) = lista.pop() {
    println!("Has sacado a {} de la lista.", pokemon.nombre);
}

println!("Lista después de hacer pop:");
lista.imprimir_lista();

Resultado Esperado:

Has sacado a Item2 de la lista.
Lista después de hacer pop:
Item4 - Tipo: Planta/Veneno, Nivel: 15
Item1 - Tipo: Eléctrico, Nivel: 25

Resumen de la primera parte #

En esta primera parte, hemos:

  • Definido una lista enlazada simple usando Option y Box.
  • Implementado métodos básicos para insertar y eliminar elementos.
  • Entendido cómo manejar propiedad y préstamos en estructuras recursivas.

Próximos pasos #

En la siguiente parte, abordaremos desafíos más avanzados:

  • Manejo de tiempos de vida y referencias.
  • Implementación de iteradores para nuestra lista enlazada.
  • Optimización y mejora de la seguridad del código.

¿Te ha resultado interesante este artículo? Te animo a que intentes implementar la lista enlazada por tu cuenta y experimentes agregando más funcionalidades, como inserción al final, búsqueda de elementos, o incluso convertirla en una lista doblemente enlazada.

Si tienes preguntas o deseas compartir tus avances, ¡deja un comentario abajo!

Próxima vez en Rustaceo: Continuaremos con “Implementando una Lista Enlazada en Rust: Parte 2”, donde profundizaremos en los iteradores y optimizaremos nuestra estructura.

¡Hasta la próxima, entrenadores y entusiastas de Rust!