9 - Implementando una lista enlazada en Rust - parte 2

9 - Implementando una lista enlazada en Rust - parte 2

¡Bienvenidos de nuevo a Rustaceo.es! En la Parte 1, comenzamos a implementar una lista enlazada simple en Rust. Como recordarás, construimos una estructura básica que nos permitía insertar Pokémon al frente de la lista y eliminar el primer pokémon. En esta segunda parte, profundizaremos en conceptos más avanzados y mejoraremos nuestra lista enlazada. Abordaremos desafíos relacionados con los tiempos de vida, implementaremos iteradores y agregaremos nuevas funcionalidades.

Objetivos de esta parte #

  • Implementar iteradores para nuestra lista enlazada.
  • Manejar correctamente los tiempos de vida y las referencias.
  • Agregar métodos adicionales como inserción al final y búsqueda.
  • Mejorar la seguridad y eficiencia de nuestra estructura.

Repaso de la estructura actual #

Recordemos la estructura de nuestra lista enlazada:

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

type Link = Option<Box<Nodo>>;

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

pub struct ListaEnlazada {
    cabeza: Link,
}

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

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

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

    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;
        }
    }
}

Implementando un iterador para la lista enlazada #

Para poder recorrer nuestra lista de forma más idiomática en Rust, implementaremos el trait Iterator. Esto nos permitirá usar for loops y otras funcionalidades que esperan iteradores.

Paso 1: definir la estructura del iterador #

Crearemos una estructura Iter que contendrá una referencia a la próxima posición en la lista.

pub struct Iter<'a> {
    actual: Option<&'a Nodo>,
}

Aquí, 'a es un tiempo de vida que asegura que las referencias dentro del iterador no vivan más que la lista original.

Paso 2: implementar un método para obtener el iterador #

En ListaEnlazada, agregamos un método iter que retorna una instancia de Iter.

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

    pub fn iter(&self) -> Iter {
        Iter { actual: self.cabeza.as_deref() }
    }
}
  • as_deref() convierte Option<&Box<Nodo>> en Option<&Nodo>.

Paso 3: implementar el trait iterator para iter #

Implementamos el trait Iterator para nuestra estructura Iter.

impl<'a> Iterator for Iter<'a> {
    type Item = &'a Pokémon;

    fn next(&mut self) -> Option<Self::Item> {
        self.actual.map(|nodo| {
            self.actual = nodo.siguiente.as_deref();
            &nodo.pokemon
        })
    }
}
  • En el método next, utilizamos map para acceder al nodo actual.
  • Actualizamos self.actual para que apunte al siguiente nodo.
  • Retornamos una referencia al pokemon actual.

Paso 4: usar el iterador en main #

Probemos el iterador en nuestro main.

fn main() {
    // ... código para crear la lista ...

    println!("Recorriendo la lista con un iterador:");
    for pokemon in lista.iter() {
        println!(
            "{} - Tipo: {}, Nivel: {}",
            pokemon.nombre, pokemon.tipo, pokemon.nivel
        );
    }
}

Resultado Esperado:

Recorriendo la lista con un iterador:
Item2 - Tipo: Fuego, Nivel: 12
Item4 - Tipo: Planta/Veneno, Nivel: 15
Item1 - Tipo: Eléctrico, Nivel: 25

Implementando un iterador mutable #

También podemos querer iterar sobre nuestra lista y modificar los elementos. Para ello, necesitamos un iterador mutable.

Paso 1: definir la estructura del iterador mutable # 

pub struct IterMut<'a> {
    actual: Option<&'a mut Nodo>,
}

Paso 2: implementar el método iter_mut #

En ListaEnlazada, agregamos:

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

    pub fn iter_mut(&mut self) -> IterMut {
        IterMut { actual: self.cabeza.as_deref_mut() }
    }
}
  • as_deref_mut() convierte Option<&mut Box<Nodo>> en Option<&mut Nodo>.

Paso 3: implementar el trait iterator para itermut # 

impl<'a> Iterator for IterMut<'a> {
    type Item = &'a mut Pokémon;

    fn next(&mut self) -> Option<Self::Item> {
        self.actual.take().map(|nodo| {
            self.actual = nodo.siguiente.as_deref_mut();
            &mut nodo.pokemon
        })
    }
}

Paso 4: usar el iterador mutable #

En main, podemos usar el iterador mutable para subir de nivel a todos los Pokémon.

for pokemon in lista.iter_mut() {
    pokemon.nivel += 1;
}

Y luego imprimir la lista actualizada:

println!("Lista después de subir de nivel a los Pokémon:");
lista.imprimir_lista();

Resultado Esperado:

Lista después de subir de nivel a los Pokémon:
Item2 - Tipo: Fuego, Nivel: 13
Item4 - Tipo: Planta/Veneno, Nivel: 16
Item1 - Tipo: Eléctrico, Nivel: 26

Agregando un método para insertar al final #

Hasta ahora, solo podemos insertar al frente de la lista. Implementemos un método insertar_al_final.

Paso 1: implementar insertar_al_final # 

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

    pub fn insertar_al_final(&mut self, pokemon: Pokémon) {
        let mut enlace = &mut self.cabeza;
        while enlace.is_some() {
            enlace = &mut enlace.as_mut().unwrap().siguiente;
        }
        *enlace = Some(Box::new(Nodo {
            pokemon,
            siguiente: None,
        }));
    }
}

Explicación:

  • Utilizamos un puntero mutable enlace que empieza en self.cabeza.
  • Iteramos hasta encontrar el None al final de la lista.
  • Asignamos un nuevo Nodo en ese lugar.

Paso 2: probar insertar_al_final #

En main, agregamos:

let item3 = Pokémon {
    nombre: String::from("Item3"),
    tipo: String::from("Agua"),
    nivel: 10,
};

lista.insertar_al_final(item3);

println!("Lista después de insertar a Item3 al final:");
lista.imprimir_lista();

Resultado Esperado:

Lista después de insertar a Item3 al final:
Item2 - Tipo: Fuego, Nivel: 13
Item4 - Tipo: Planta/Veneno, Nivel: 16
Item1 - Tipo: Eléctrico, Nivel: 26
Item3 - Tipo: Agua, Nivel: 10

Agregando un método para buscar un pokemon #

Implementemos un método que nos permita buscar un Pokémon por nombre.

Paso 1: implementar buscar_elemento # 

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

    pub fn buscar_elemento(&self, nombre: &str) -> Option<&Pokémon> {
        let mut actual = &self.cabeza;
        while let Some(nodo) = actual {
            if nodo.pokemon.nombre == nombre {
                return Some(&nodo.pokemon);
            }
            actual = &nodo.siguiente;
        }
        None
    }
}

Paso 2: probar buscar_elemento #

En main, agregamos:

if let Some(pokemon) = lista.buscar_elemento("Item1") {
    println!(
        "Encontrado: {} - Tipo: {}, Nivel: {}",
        pokemon.nombre, pokemon.tipo, pokemon.nivel
    );
} else {
    println!("Pokémon no encontrado.");
}

Resultado Esperado:

Encontrado: Item1 - Tipo: Eléctrico, Nivel: 26

Manejando tiempos de vida y seguridad #

Al implementar iteradores y métodos adicionales, es importante asegurarse de que nuestras referencias y tiempos de vida sean correctos para evitar errores en tiempo de compilación.

Importancia de los tiempos de vida #

  • Los tiempos de vida (lifetimes) aseguran que las referencias no vivan más allá de los datos a los que apuntan.
  • Al implementar iteradores, especificamos los tiempos de vida para vincular las referencias al tiempo de vida de la lista.

Ejemplo de tiempos de vida en el iterador # 

pub struct Iter<'a> {
    actual: Option<&'a Nodo>,
}
  • El tiempo de vida 'a indica que Iter no puede vivir más que la referencia a ListaEnlazada.

Mejorando la eficiencia con rc y refcell #

Hasta ahora, nuestra lista es unidireccional y no permite múltiples propietarios ni mutabilidad interior. Si queremos una lista más flexible, podemos usar Rc<T> y RefCell<T>.

Advertencia #

  • Usar Rc y RefCell agrega complejidad y puede introducir riesgos si no se maneja correctamente.
  • Para este ejemplo, mantendremos nuestra implementación simple y segura.

Resumen de la segunda parte #

En esta segunda parte, hemos:

  • Implementado iteradores para recorrer nuestra lista de forma idiomática.
  • Agregado métodos adicionales como insertar_al_final y buscar_elemento.
  • Manejado tiempos de vida para asegurar la seguridad de nuestras referencias.
  • Mejorado nuestra comprensión de las estructuras de datos y cómo implementarlas en Rust.

Próximos pasos #

Para seguir mejorando nuestra lista enlazada:

  • Implementar métodos de eliminación más específicos, como eliminar un Pokémon por nombre.
  • Convertir la lista en doblemente enlazada, permitiendo iteración en ambos sentidos.
  • Utilizar patrones de diseño para mejorar la modularidad y reutilización del código.

¿Te ha resultado útil este artículo? Implementar estructuras de datos en Rust es una excelente manera de profundizar en el lenguaje y comprender cómo maneja la memoria y las referencias. Te animo a seguir experimentando y expandiendo la funcionalidad de tu lista enlazada.

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

Hasta la próxima en Rustaceo, donde continuaremos explorando el fascinante mundo de Rust y la programación de sistemas.