Listas enlazadas de Ruby

Para este ejercicio, implementaremos una versión simple de una lista enlazada única. Pero primero, aprendamos qué es una lista vinculada y por qué debería importarte.

Una estructura de datos de lista vinculada a, utilizada para inserciones y eliminaciones rápidas y eficientes en memoria. A diferencia de los arrays, que son objetos individuales, las listas enlazadas contienen varios objetos de ‘nodo’ que están vinculados entre sí a través de referencias.

Las listas enlazadas se pueden vincular de forma individual o doble. Por ahora, nos centraremos en las listas enlazadas por separado.

Lista vinculada única

Si las listas vinculadas son varios objetos vinculados entre sí, lo ideal es que necesitemos un par de objetos diferentes.

  1. Una LinkedList objeto, que contiene todos los objetos en la lista

  2. Un Nodo de objeto, que contiene los datos del elemento, así como una referencia al siguiente Nodo en la lista.

Espera, ¿por qué no utilizar las matrices de lugar?

En lenguajes de nivel inferior, los arrays se asignan en bloques. Por lo tanto, los arrays son de tamaño estático y solo pueden contener un tipo de datos específico. Las listas vinculadas almacenan datos en el montón, lo que significa que los datos se pueden almacenar de forma no organizada. Dado que cada nodo apunta al siguiente, aún es posible mantener la estructura de listas.

introducción

La mejor manera de entender cómo listas enlazadas trabajo es hacer uno! Hagámoslo en Ruby. Este es el proceso.

  1. Comience creando una clase Node. Tendremos atributos para representar los datos (llamemos a esto @data) y la referencia al siguiente nodo (llamemos a esto @next).

  2. Cree una clase LinkedList. Esta clase tendrá dos valores, @head y @tail. Estos representarán el principio y el final de la lista. Inicialice ambos a nil por ahora. Tenemos una lista vacía!

  3. Ahora, para incorporar las dos clases juntas. Cree un método en la clase LinkedList llamado insert_front. El reto es añadir un elemento al principio de la lista. Esto se puede hacer creando un nuevo Node y, a continuación, haciendo lo siguiente:

  4. Almacene el valor de @head en una variable temporal

  5. Establezca @head en el Node recién creado. Tenga en cuenta que actualmente, su referencia next es nil.

  6. Piensa en lo que necesitaríamos hacer si estamos agregando un nuevo elemento al comienzo de una lista vinculada. Consulte el diagrama (sugerencia: tendremos que hacer algo con la referencia next del nuevo nodo)

  7. Por último, maneje el caso especial de @tail. @tail siempre debe ser el último Node en la lista vinculada.

  8. Cree otro método en LinkedList o Node llamado to_s para imprimir la lista en la consola.

Iterar sobre Listas vinculadas

Use bucles while para iterar sobre listas vinculadas. Los bucles While son mejores que los bucles for aquí porque las listas enlazadas no tienen una propiedad de longitud. En lugar de iterar for un cierto número de veces, simplemente iteramos while nuestro puntero current no es nil.

Cree una variable local llamada current que comience apuntando al nodo raíz de la lista. Dentro del bucle puedes hacer dos cosas:

  1. acceda al valor del nodo actual en current.data

  2. apunte la variable actual al siguiente elemento con current = current.next

BONO: Crea un método insert_end para agregar nodos al final de la lista.

SUPER BONUS: Crea un método insert más versátil para agregar un nodo en cualquier lugar de la lista vinculada, proporcionando un índice para el nuevo elemento.

Deja una respuesta

Tu dirección de correo electrónico no será publicada.