Las listas vinculadas son una estructura de datos habitual en informática. Puedes utilizar una lista vinculada para representar una lista de reproducción de música o un historial de acciones, por ejemplo.
Resumen
Una lista vinculada es una estructura de datos lineal en la que cada elemento almacena una referencia al siguiente elemento de la lista. Cada elemento de una lista vinculada se llama nodo. Un nodo es un contenedor que alberga algunos datos y una referencia al siguiente nodo.
Al vincular distintos nodos en una secuencia se crea una lista vinculada. El primer nodo de la lista se llama nodo de inicio y el último nodo se llama nodo de fin. Para recorrer la lista, empiezas en el inicio y te desplazas hasta el siguiente elemento utilizando la referencia de cada nodo.
Cuándo usar estas listas
Las listas vinculadas son un buen punto de partida para implementar otras estructuras de datos, como pilas o colas. Las listas vinculadas son una forma sencilla de almacenar datos para el acceso secuencial y admiten la inserción rápida de nuevos elementos. A diferencia de las matrices, las listas vinculadas no son contiguas (están una al lado de la otra) en la memoria. Esto significa que un nodo puede estar en cualquier lugar de la memoria y la referencia al siguiente nodo te indica su ubicación. Para insertar o eliminar nodos de una lista vinculada, basta con cambiar las referencias al nodo siguiente.
Cuándo no usar estas listas
Si tu programa requiere un acceso aleatorio a los elementos (como elegir un jugador al azar de una lista), las listas vinculadas carecen de esta funcionalidad. Las listas vinculadas son menos eficaces que las matrices si necesitas acceder a un nodo concreto de la mitad de la lista, ya que tendrás que empezar por el inicio y recorrerla hasta el nodo concreto que necesites.
Implementación en Verse
La API de Verse no tiene una implementación incorporada de listas vinculadas, pero puedes crear una por tu cuenta.
Las listas vinculadas están formadas por nodos y tendrás que definir una clase para representarlas. A continuación, se muestra un ejemplo de nodo de tipo genérico:
list_node := class<unique>:
var Next:?list_node = false
Data:any = {}
Aquí la variable de opción Next almacena una referencia al siguiente nodo de la lista, que es de tipo list_node. Ten en cuenta que Next tiene que ser una variable option, porque puede que un nodo no siempre tenga un nodo siguiente al que apuntar (como el nodo de fin de una lista vinculada). Si quieres cambiar dinámicamente la vinculación de tu lista, Next debe ser un var. El nodo también contiene algún valor, que se almacena en Data. Como se trata de un nodo de tipo genérico, Data es de tipo any y el nodo podría contener cualquier tipo de datos. Podría ser un tipo común, un contenedor, ¡o incluso otra lista vinculada!
Node1 := list_node{ Next := false, Data := 1 } # Un entero
Node2 := list_node{ Next := false, Data := "String" } # Una cadena
Node3 := list_node{ Next := false, Data := []int} # Una matriz
Node4 := list_node{ Next := false, Data := list_node } # La clase list_node
Node5 := list_node{ Next := false, Data := Node1 } # El primer nodo
El especificador <unique> permite que list_node sea comparable. Esto te permite comprobar si un nodo es igual a algún otro nodo, por ejemplo, comprobar si tu nodo es el inicio o el fin de una lista.
Si necesitas una implementación más específica, como un nodo que solo maneje números o cadenas, asegúrate de cambiar el tipo de Data para que coincida. Si Data es de tipo comparable, puedes comparar el valor de Data con otro valor para encontrar un nodo concreto.
Listas vinculadas de un único enlace
El tipo más básico de lista vinculada es una lista de un único enlace, en la que cada nodo contiene una referencia al nodo siguiente (un único enlace). Para convertir tus nodos en una lista, vincúlalos utilizando las referencias Next de cada nodo.
# Enlaza cada nodo con el siguiente nodo de la lista.
set Node1.Next = option{Node2}
set Node2.Next = option{Node3}
set Node3.Next = option{Node4}
set Node4.Next = option{Node5}
Aunque tus nodos estén enlazados, debes definir tu lista vinculada en una clase. Esto facilitará la realización de funciones utilizando tu lista, en lugar de hacer referencia a tu primer nodo cada vez.
linked_list := class:
var Head:list_node
Una clase linked_list básica solo contiene una referencia al nodo de inicio. Para crear una instancia de tu clase linked_list, vincula tus nodos entre sí y, a continuación, crea instancias de tu lista utilizando el nodo de inicio.
# Crea una lista vinculada con Node1 como inicio.
BasicList:linked_list = linked_list{Head := Node1}
Para recorrer la lista, empieza en el nodo de inicio e itera por la lista, deteniéndote en el final. Puedes hacerlo en una función externa o en una función de clase dentro de tu clase linked_list. A continuación, se proporciona una función de ejemplo que recorre toda la lista de inicio a fin:
linked_list := class:
var Head:list_node
TraverseList():void=
var CurrentNode:?list_node := option{Head} # El nodo en el que estás actualmente
var NodeNumber:int = 1 # El número del nodo actual
Print("Empezando por el nodo de inicio...")
# Si el nodo actual tiene un nodo a continuación, establece el nodo actual en
# el siguiente nodo de la lista.
loop:
if(NextNode := CurrentNode?.Next?):
set CurrentNode = option{NextNode}
set NodeNumber += 1
Print("¡Accediendo al nodo {NodeNumber}!")
else:
Print("No hay ningún nodo a continuación. ¡Este es el nodo de fin!")
break
Aquí la función TraverseList() comprueba si CurrentNode contiene una referencia Next y la almacena en NextNode. Si es así, establece CurrentNode en NextNode repetidamente hasta llegar al nodo de fin. El nodo de fin no tiene una referencia Next, por lo que el bucle se detiene aquí.
Listas vinculadas de doble enlace
A diferencia de las listas vinculadas de un único enlace, los nodos de una lista vinculada de doble enlace también contienen una referencia al nodo que le precede, llamado nodo anterior.
doubly_linked_node := class<unique>:
var Next:?doubly_linked_node = false
var Previous:?doubly_linked_node = false
Data:any = {}
Esto significa que puedes recorrer los nodos de una lista vinculada de doble enlace tanto hacia delante como hacia atrás. Esto puede hacerse en una función externa o en una función de clase. A continuación, se proporciona una función de ejemplo que recorre la lista de inicio a fin y viceversa:
doubly_linked_list := class():
Head:doubly_linked_node
# Recorre una lista vinculada, pero tanto hacia delante como hacia atrás.
TraverseDoublyLinkedList():void=
var CurrentNode:?doubly_linked_node := option{Head}
var NodeNumber:int = 1
Print("Empezando por el nodo de inicio y siguiendo hacia delante...")
loop:
if(NextNode := CurrentNode?.Next?):
set CurrentNode = option{NextNode}
set NodeNumber += 1
Print("¡Accediendo al nodo {NodeNumber}!")
else:
Print("No hay ningún nodo a continuación. ¡Este es el nodo de fin!")
break
Print("Ahora retrocedamos hasta el nodo de inicio...")
loop:
if(PreviousNode := CurrentNode?.Previous?):
set CurrentNode = option{PreviousNode}
set NodeNumber -= 1
Print("¡Accediendo al nodo {NodeNumber}!")
else:
Print("No hay nodo anterior. Volvemos al nodo de inicio.")
break
Listas vinculadas circulares
En una lista vinculada circular, el nodo de inicio está vinculado al nodo de fin. Esto significa que puedes recorrer toda la lista más allá del nodo de fin y llegar de nuevo al inicio. Las listas vinculadas circulares pueden ser de un único o doble enlace. El único requisito es que el nodo de inicio se vincule con el de fin, o viceversa.
Iteradores
Un iterador es un objeto que te permite iterar sobre un contenedor y realizar operaciones en todo el proceso. Imagínalo como un vagón de tren lleno de pasajeros. El tren viaja por una vía, parando en cada estación del trayecto. En cada estación, el tren realiza una tarea, como subir o bajar pasajeros. En las listas vinculadas, cada estación es un nodo de la lista. El tren (iterador) recorre la lista hasta cada nodo y puede realizar operaciones donde se detenga.
Los iteradores son útiles para las listas vinculadas porque te permiten realizar operaciones en lugares concretos, en lugar de solo en el nodo de inicio o de fin.
linked_list_iterator := class:
List:linked_list
var CurrentNode:list_node
# Si hay un NextNode al que pueda viajar el iterador, lo hará.
Next()<transacts><decides>:list_node=
set CurrentNode = CurrentNode.Next?
Aquí el iterador contiene una referencia a la lista sobre la que itera y un CurrentNode donde el iterador se detiene actualmente. La función Next() comprueba si el CurrentNode tiene un nodo a continuación y salta a ese nodo. Observa que Next() aquí incluye los especificadores <transacts> y <decides>. La función debe ser <transacts>, ya que actualiza la var CurrentNode, y te interesa incluir <decides>, ya que hacer que Next() falle te permite saber si has iterado al siguiente nodo o no.
Aunque pueda parecer que un iterador debe empezar en el inicio de una lista, en realidad tiene que empezar antes del inicio. Esto es para que el iterador pueda realizar operaciones en el nodo de inicio, como insertar nodos antes del inicio o eliminar el inicio por completo.
Para inicializar el iterador antes del inicio, puedes inicializar CurrentNode a un nodo ficticio con el inicio de la lista como siguiente nodo. En Verse, no puedes acceder a List al inicializar CurrentNode porque no se puede acceder a la variable de los miembros de la clase desde el mismo ámbito, solo desde ámbitos diferentes, como dentro de una función.
linked_list_iterator := class:
List:linked_list
# La línea siguiente fallará porque no puedes acceder a List desde este ámbito.
var CurrentNode:list_node := list_node{Next := option{List.Head}}
En su lugar, para instanciar un iterador puedes utilizar una función constructor. Un constructor es un tipo compuesto que crea una instancia de la clase a la que está asociado. El constructor establece los valores iniciales de un objeto y te permite acceder al valor de la lista y asignar CurrentNode a su inicio.
# Construye un iterador con CurrentNode como nodo ficticio antes del inicio de la lista indicada.
MakeIterator<constructor>(List:linked_list) := linked_list_iterator:
List := List
# Puedes acceder a List desde este ámbito en una función constructor.
CurrentNode:= list_node{Next := option{List.Head}}
linked_list_iterator := class:
List:linked_list
var CurrentNode:list_node
La inicialización de un iterador para una lista vinculada de doble enlace es muy parecida, salvo que la inicializas utilizando nodos de doble enlace.
# Construye un iterador con CurrentNode como nodo ficticio antes del inicio de la lista indicada.
MakeDoublyLinkedIterator<constructor>(List:doubly_linked_list) := doubly_linked_list_iterator:
List := List
# Puedes acceder a List desde este ámbito en una función constructor.
CurrentNode:= doubly_linked_node{Next := option{List.Head}}
doubly_linked_list_iterator := class:
List:doubly_linked_list
var CurrentNode:doubly_linked_node
Cómo iterar entre nodos
Puedes desplazar el iterador hacia delante o hacia atrás en función de la vinculación de tu lista. Los iteradores de una lista vinculada solo pueden ir hacia delante, mientras que los de una lista vinculada de doble enlace pueden ir en cualquier dirección. Esta funcionalidad se define en dos funciones: Next() y Previous(). Recuerda que las listas vinculadas de un único enlace no tienen una función Previous(). Las listas vinculadas circulares pueden tener una u otra función según sean de un único o doble enlace.
# Si hay un NextNode al que pueda viajar el iterador, lo hará.
Next()<transacts><decides>:doubly_linked_node=
set CurrentNode = CurrentNode.Next?
# Si hay un PreviousNode al que pueda viajar el iterador, lo hará.
Previous()<transacts><decides>:doubly_linked_node=
set CurrentNode = CurrentNode.Previous?
Cómo añadir nodos
Puedes utilizar iteradores para añadir nodos a lugares concretos de la lista vinculada. Cuando se añade un nodo, elegir dónde añadirlo es importante. Podrías añadir el nodo antes o después del nodo actual, pero esto depende de la estructura de tu lista. En una lista vinculada de un único enlace, solo puedes añadir nodos después de otros nodos, porque no tienes una referencia de nodo Previous a la que referirte. En una lista vinculada de doble enlace, puedes añadir nodos antes o después de otros nodos.
# Añade un nuevo nodo después de CurrentNode.
AddNextNode(NewNode:list_node):void=
if(NextNode := CurrentNode.Next?):
set NewNode.Next = option{NextNode}
set CurrentNode.Next = option{NewNode}
Print("¡Nuevo nodo añadido correctamente!")
else:
set CurrentNode.Next = option{NewNode}
Print("¡Nuevo nodo añadido correctamente al final de la lista!")
Aquí la función AddNode añade un nodo entre CurrentNode y el nodo siguiente. Lo consigue:
-
Estableciendo la referencia
NextdeCurrentNodeaNewNode. -
Estableciendo la referencia
NextdeNewNodeaNextNode. Si no hayNextNode(por ejemplo, en el fin de una lista), la función solo estableceNewNodecomo nodo siguiente.
In a doubly linked list, you have the option of adding nodes before or after CurrentNode. You can split this functionality into two functions, AddNodeAfter() and AddNodeBefore(). The implementation is very similar to the one in the singly linked list, except that you have to remember to set the Previous reference for each node as well.
# Añade un nuevo nodo después de CurrentNode.
AddNodeAfter(NewNode:doubly_linked_node):void=
if(NextNode := CurrentNode.Next?):
set NewNode.Next = option{NextNode}
set NewNode.Previous = option{CurrentNode}
set CurrentNode.Next = option{NewNode}
set NextNode.Previous = option{NewNode}
Print("¡Nuevo nodo añadido correctamente!")
else:
set CurrentNode.Next = option{NewNode}
Print("¡Nuevo nodo añadido correctamente al final de la lista!")
# Añade un nuevo nodo antes de CurrentNode.
AddNodeBefore(NewNode:doubly_linked_node):void=
if(PreviousNode := CurrentNode.Previous?):
set NewNode.Next = option{CurrentNode}
set NewNode.Previous = option{PreviousNode}
set CurrentNode.Previous = option{NewNode}
set PreviousNode.Next = option{NewNode}
Print("¡Nuevo nodo añadido correctamente!")
else:
set NewNode.Next = option{CurrentNode}
set CurrentNode.Previous = option{NewNode}
Print("¡Nuevo nodo añadido correctamente al final de la lista!")
Cómo eliminar nodos
Para eliminar nodos, tienes que eliminar todas las referencias a ese nodo conservando el orden de la lista. Para ello, si el nodo que quieres eliminar tiene algún nodo después, tienes que vincular los nodos anteriores al nodo eliminado con los nodos posteriores. En una lista vinculada de un único enlace, como no tienes una referencia Previous, solo puedes eliminar los nodos posteriores a CurrentNode.
# Elimina el siguiente nodo después de CurrentNode. Si el siguiente nodo
# tiene una referencia Next, establece ese nodo en el siguiente nodo de CurrentNode
RemoveNextNode():void=
if(RemovedNode := CurrentNode.Next?):
if(NodeAfter := RemovedNode.Next?, set RemovedNode.Next = false):
set CurrentNode.Next = option{NodeAfter}
Print("Se ha eliminado el nodo entre CurrentNode y el nodo siguiente")
# Si el nodo eliminado es el nodo de inicio, establece el siguiente nodo como nuevo inicio.
if(RemovedNode = List.Head):
Print("El nodo eliminado era el nodo de inicio, estableciendo el nodo posterior como nuevo inicio")
set List.Head = NodeAfter
else:
set CurrentNode.Next = false
Print("Se ha eliminado el nodo antes de CurrentNode")
else:
Print("No se ha podido eliminar el nodo")
Ten en cuenta que necesitas un caso especial cuando elimines del nodo de inicio. En este caso, tienes que establecer el nodo situado después del nodo de inicio como nuevo inicio; de lo contrario tu lista vinculada no tendrá un lugar desde el que empezar.
Al igual que al añadir nodos, eliminar nodos de una lista vinculada de doble enlace puede dividirse en eliminar el nodo anterior o posterior al nodo actual.
# Elimina el nodo después de CurrentNode.
RemoveNodeAfter():void=
if(RemovedNode := CurrentNode.Next?):
if:
NodeAfter := RemovedNode.Next?
set RemovedNode.Next = false
set RemovedNode.Previous = false
set NodeAfter.Previous = option{CurrentNode}
set CurrentNode.Next = option{NodeAfter}
then:
Print("Se ha eliminado el nodo entre CurrentNode y el nodo siguiente")
# Si el nodo eliminado es el nodo de inicio, establece el siguiente nodo como nuevo inicio.
if(RemovedNode = List.Head):
Print("El nodo eliminado era el nodo de inicio, estableciendo el nodo posterior como nuevo inicio")
set List.Head = NodeAfter
# No te interesa poder regresar al nodo ficticio,
# así que establece el nuevo Previous del inicio como false.
set NodeAfter.Previous = false
else:
set CurrentNode.Next = false
Print("Se ha eliminado el nodo después de CurrentNode")
else:
Print("No se ha podido eliminar el nodo")
# Elimina el nodo antes de CurrentNode.
RemoveNodeBefore():void=
if(RemovedNode := CurrentNode.Previous?):
if:
NodeBefore := RemovedNode.Previous?
set RemovedNode.Previous = false
set CurrentNode.Previous = option{NodeBefore}
set NodeBefore.Next = option{CurrentNode}
then:
Print("Se ha eliminado el nodo entre CurrentNode y el nodo que le precede")
# Si el nodo eliminado es el nodo de inicio, establece el siguiente nodo como nuevo inicio.
else:
set CurrentNode.Previous = false
if(RemovedNode = List.Head):
Print("El nodo eliminado era el nodo de inicio, estableciendo el nodo posterior como nuevo inicio")
set List.Head = CurrentNode
Print("Se ha eliminado el nodo después de CurrentNode")
else:
Print("No se ha podido eliminar el nodo")
Por tu cuenta
Existen varias formas de mejorar las listas vinculadas y puedes explorar diferentes maneras de añadir funcionalidad. A continuación, te indicamos varias formas de mejorar tus listas vinculadas:
-
¿Y si cada lista almacenara también una referencia al nodo de fin?
-
¿Puedes implementar un método
ToString()para imprimir el contenido de tus nodos? -
¿E invertir una lista? ¿Puedes implementar una función
Length()? -
¿Puedes añadir más métodos al iterador para hacer nuevas operaciones?