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.
-
Una LinkedList objeto, que contiene todos los objetos en la lista
-
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.
-
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). -
Cree una clase
LinkedList. Esta clase tendrá dos valores,@heady@tail. Estos representarán el principio y el final de la lista. Inicialice ambos anilpor ahora. Tenemos una lista vacía! -
Ahora, para incorporar las dos clases juntas. Cree un método en la clase
LinkedListllamadoinsert_front. El reto es añadir un elemento al principio de la lista. Esto se puede hacer creando un nuevoNodey, a continuación, haciendo lo siguiente: -
Almacene el valor de
@headen una variable temporal -
Establezca
@headen elNoderecién creado. Tenga en cuenta que actualmente, su referencianextesnil. -
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
nextdel nuevo nodo) -
Por último, maneje el caso especial de
@tail.@tailsiempre debe ser el últimoNodeen la lista vinculada. -
Cree otro método en
LinkedListoNodellamadoto_spara 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:
-
acceda al valor del nodo actual en
current.data -
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.