Listas vinculadas

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:

# A container node that contains data and a reference
# to the next node in the list.
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 } # An int
Node2 := list_node{ Next := false, Data := "String" } # A string
Node3 := list_node{ Next := false, Data := []int} # An array
Node4 := list_node{ Next := false, Data := list_node } # list_node class
Node5 := list_node{ Next := false, Data := Node1 } # The first node

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.

# A container node that contains integer data and a reference
# to the next node in the list.
list_node_int := class(list_node):
    # Reference to the next node in the list.
    var Next<override>:?list_node = false
    Data<override>:int

# A container node that contains string data and a reference
# to the next node in the list.
list_node_string := class(list_node):

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.

# Link each Node to the next Node in the list
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.

# A data structure that links multiple list_node structures together to create a chain. 
# Uses singly linked nodes which contain a reference to the next node in the chain.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.

# Create a Linked List with node1 as the head.
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:

# A data structure that links multiple list_node structures together to create a chain. 
# Uses singly linked nodes which contain a reference to the next node in the chain.linked_list := class:
    var Head:list_node

    TraverseList():void=
        var CurrentNode:?list_node := option{Head} # The node you're currently on
        var NodeNumber:int = 1 # The number of the current node
        Print("Starting at the Head Node...")
        # If the current node has a next node, set the current node to
        # the next node in the list

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.

# A container node that contains data and a reference to both
# the next and previous nodes in the list.
doubly_linked_node := class<unique>:
    var Next:?doubly_linked_node = false
    var Previous:?doubly_linked_node = false
    Data:any = {}

Al igual que sucede con los nodos de un solo enlace, si necesitas una implementación más específica que solo maneje ciertos tipos de datos, asegúrate de cambiar el tipo de Data para que coincida.

# A container node that contains integer data and a reference to both
# the next and previous nodes in the list.
doubly_linked_int_node := class(doubly_linked_node):
    Data<override>:int

# A container node that contains string data and a reference to both
# the next and previous nodes in the list.
doubly_linked_string_node := class(doubly_linked_node):
    Data<override>:string

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:

# A data structure that links multiple list_node structures together to create a chain. 
# Uses doubly linked nodes which contain references to both the next and previous nodes.
doubly_linked_list := class():
    var Head:doubly_linked_node

    # Traverse a LinkedList, but both backward and forward!
    TraverseDoublyLinkedList():void=
        var CurrentNode:?doubly_linked_node := option{Head}
        var NodeNumber:int = 1
        Print("Starting at the Head Node, and going forward...")

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.

# Iterates over a linked_list and can add nodes or remove nodes as it iterates.
linked_list_iterator := class:
    List:linked_list
    var CurrentNode:list_node

    # If there is a NextNode for the iterator to travel to, travel to that node
    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 está detenido actualmente. La función Next() comprueba si el CurrentNode tiene un nodo a continuación y salta a ese nodo. Ten en cuenta que Next() 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
    # The below line will fail because you can't access List from this scope
    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.

# Construct an Iterator with CurrentNode as a dummy node before the head of the given list.
MakeIterator<constructor>(List:linked_list) := linked_list_iterator:
    List := List
    # You can access List from this scope in a constructor function
    CurrentNode:= list_node{Next := option{List.Head}}

# Iterates over a linked_list and can add nodes or remove nodes as it iterates.
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.

# Construct an Iterator with CurrentNode as a dummy node before the head of the given list.
MakeDoublyLinkedIterator<constructor>(List:doubly_linked_list) := doubly_linked_list_iterator:
    List := List
    # You can access List from this scope in a constructor function
    CurrentNode:= doubly_linked_node{Next := option{List.Head}}

# Iterates over a doubly_linked_list and can add nodes or remove nodes as it iterates.
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.

# If there is a NextNode for the iterator to travel to, travel to that node
Next()<transacts><decides>:doubly_linked_node=
    set CurrentNode = CurrentNode.Next?

# If there is a PreviousNode for the iterator to travel to, travel to that node
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.

# Adds a new node after CurrentNode.
AddNextNode(NewNode:list_node):void=
    if(NextNode := CurrentNode.Next?):
        set NewNode.Next = option{NextNode}
        set CurrentNode.Next = option{NewNode}
        Print("Successfully added a new node!")
    else:
        set CurrentNode.Next = option{NewNode}
        Print("Successfully added a new node to the tail of the list!")

Aquí la función AddNode añade un nodo entre CurrentNode y el nodo siguiente. Lo consigue:

• Estableciendo la referencia Next de CurrentNode a NewNode.

• Estableciendo la referencia Next de NewNode a NextNode. Si no hay NextNode (por ejemplo, en el fin de una lista), la función solo establece NewNode como nodo siguiente.

En una lista vinculada de doble enlace, puedes añadir nodos antes o después de CurrentNode. Puedes dividir esta funcionalidad en dos funciones: AddNodeAfter() y AddNodeBefore(). La implementación es muy similar a la de la lista vinculada de un único enlace, salvo que tienes que acordarte de establecer también la referencia Previous para cada nodo.

# Adds a new node after 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("Successfully added a new node!")
    else:
        set CurrentNode.Next = option{NewNode}

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.

# Remove the next node after CurrentNode. If the next node
# has a Next reference, set that node to the next node of CurrentNode.
RemoveNextNode():void=
    if(RemovedNode := CurrentNode.Next?):
        if(NodeAfter := RemovedNode.Next?, set RemovedNode.Next = false):
            set CurrentNode.Next = option{NodeAfter}
            Print("Removed the node between CurrentNode and the node after it")
            # If the removed node is the Head node, set the next node as the new Head.
            if(RemovedNode = List.Head):
                Print("Removed node was the head node, setting the node after as the new head")

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.

# Remove the node after 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:

Código completo

A continuación, puedes ver el código completo para cada clase de este ejemplo:

list_node

# A container node that contains data and a reference
# to the next node in the list.
list_node := class<unique>:
    # Reference to the next node in the list.
    var Next:?list_node = false
    Data:any = {}


# A container node that contains integer data and a reference
# to the next node in the list.

linked_list

# A data structure that links multiple list_node structures together to create a chain. 
# Uses singly linked nodes which contain a reference to the next node in the chain.
linked_list := class:
    # The first node in the list.
    var Head:list_node
 
    # Traverses the linked list forward starting from the CurrentNode.
    TraverseList():void=
        var CurrentNode:?list_node := option{Head} # The node you're currently on
        var NodeNumber:int = 1 # The number of the current node.

linked_list_iterator

# Iterates over a linked_list and can add nodes or remove nodes as it iterates.
linked_list_iterator := class:
    List:linked_list
    var CurrentNode:list_node

    # If there is a NextNode for the iterator to travel to, travel to that node.
    Next()<transacts><decides>:list_node=
        NextNode := CurrentNode.Next?
        set CurrentNode = NextNode

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?