Listas enlazadas

Las listas enlazadas son una estructura de datos habitual en ciencias de la computación. Puedes utilizar una lista enlazada para representar, por ejemplo, una lista de reproducción de música o un historial de acciones.

Información general

Una lista enlazada 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 enlazada se denomina nodo. Un nodo es un contenedor que tiene datos y una referencia al siguiente nodo.

La unión de diferentes nodos en una secuencia crea una lista enlazada. El primer nodo de una lista se denomina nodo inicial, y el último nodo se denomina nodo final. Para recorrer la lista, se empieza en el inicial y se viaja hasta el siguiente elemento mediante la referencia de cada nodo.

Cuándo usarlas

Las listas enlazadas son un buen punto de partida para implementar otras estructuras de datos, como acumulaciones o colas. Las listas enlazadas 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 enlazadas no son contiguas (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 indica la ubicación. Para insertar o eliminar nodos de una lista enlazada, solo hace falta cambiar las referencias al nodo que aparece a continuación.

Cuándo no usarlas

Si tu programa requiere un acceso aleatorio a los elementos (como elegir un jugador al azar de una lista), las listas enlazadas carecen de esta funcionalidad. Las listas enlazadas son menos eficientes que las matrices si necesitas acceder a un nodo en particular en medio de la lista, ya que tendrás que empezar desde el nodo inicial y recorrer hasta el nodo en particular que necesites.

Implementación en Verse

La API de Verse no tiene una implementación integrada de las listas enlazadas, pero puedes crear una por tu cuenta.

Las listas enlazadas se componen de nodos, por lo que tendrás que definir una clase para representarlos. A continuación, se muestra un ejemplo de un tipo genérico de nodo:

# 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 un nodo puede que no siempre tenga un nodo siguiente al que apuntar (como el nodo final de una lista enlazada). Si quieres cambiar el enlace de tu lista de manera dinámica, Next tiene que ser un var. El nodo también contiene algún valor, que se almacena en Data. Dado que se trata de un tipo genérico de nodo, Data es de tipo any, y el nodo podría contener cualquier tipo de dato. Puede ser un tipo común, un contenedor o incluso otra lista enlazada.

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. Te permite comprobar si un nodo es igual a otro, por ejemplo, si tu nodo es inicial o final en 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 según coincida. Si Data es de tipo comparable, puedes comparar el valor de Data con otro valor para encontrar un nodo específico.

# 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 enlazadas simples

El tipo más básico de lista enlazada es una lista enlazada simple, en la que cada nodo contiene una referencia al nodo siguiente (un único enlace). Para convertir tus nodos en una lista, enlázalos mediante 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, deberás definir tu lista enlazada en una clase. Esto facilitará la realización de funciones con 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 inicial. Para crear una instancia de tu clase linked_list, enlaza tus nodos; luego, instancia tu lista con el nodo inicial.

# Create a Linked List with node1 as the head.
BasicList:linked_list = linked_list{Head := Node1}

Para recorrer la lista, se empieza en el nodo inicial y se itera a través de la lista, hasta llegar al 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 detalla una función de ejemplo en la que se recorre toda la lista desde el nodo inicial hasta el nodo final:

# 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 a NextNode repetidamente hasta alcanzar el nodo final. El nodo final no tiene referencia Next, por lo que el bucle se detiene aquí.

Listas doblemente enlazadas

A diferencia de las listas enlazadas simples, los nodos de una lista doblemente enlazada también contienen una referencia al nodo que les preceden, 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 con los nodos enlazados simples, 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 doblemente enlazada 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 detalla una función de ejemplo en la que se recorre la lista desde el nodo inicial hasta el final 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 enlazadas circulares

En una lista enlazada circular, el nodo inicial está enlazado con el final. Esto significa que puedes recorrer toda la lista más allá del nodo final y así volver al nodo inicial. Las listas enlazadas circulares pueden tener un enlace simple o doble, el único requisito es que el nodo inicial esté enlazado con el final o viceversa.

Iteradores

Un iterador es un objeto que permite iterar sobre un contenedor y realizar operaciones a lo largo del camino. Puedes verlo como si fuera un vagón de tren lleno de pasajeros. El tren se desplaza por una vía y se detiene en cada estación del trayecto. En cada estación, el tren realiza una tarea, como subir o bajar pasajeros. En las listas enlazadas, cada estación es un nodo de la lista. El tren (iterador) recorre la lista a cada nodo y puede realizar operaciones donde se detiene.

Los iteradores son útiles para las listas enlazadas porque permiten realizar operaciones en lugares específicos, en lugar de solo realizarlas en el nodo inicial o final.

# 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á actualmente detenido. La función Next() comprueba si el CurrentNode tiene un nodo después de él y, luego, salta a ese nodo. Ten en cuenta que Next() aquí incluye los especificadores <transacts> y <decides>. La función debe ser <transacts> ya que actualiza la var CurrentNode, y deberías incluir <decides>, ya que si haces que Next() sea falible sabrás si iteraste 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 nodo inicial. Esto es para que el iterador pueda realizar operaciones en el nodo inicial, como insertar nodos antes del inicial o eliminar el inicial por completo.

Para inicializar el iterador antes del nodo inicial, puedes inicializar CurrentNode en un nodo ficticio con el nodo inicial de la lista como el nodo siguiente. En Verse, no se puede acceder a la List al inicializar CurrentNode, porque no se puede acceder a la variable de los miembros de la clase desde el mismo ámbito, solo desde diferentes ámbitos 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 permite acceder al valor de Lista y asignar CurrentNode a su nodo inicial.

# 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 doblemente enlazada es muy similar, salvo que se inicializa mediante nodos doblemente enlazados.

# 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

Iteración entre nodos

Puedes mover el iterador hacia delante o hacia atrás en función del enlace de tu lista. Los iteradores de una lista enlazada simple solo pueden desplazarse hacia delante, mientras que los iteradores de una lista enlazada doble pueden desplazarse en cualquier dirección. Esta funcionalidad se define en dos funciones, Next() y Previous(). Recuerda que las listas enlazadas simples no tendrán una función Previous(). Las listas enlazadas circulares pueden tener una u otra función en función de si tienen un enlace simple o doble.

# 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 específicos de la lista enlazada. Al añadir un nodo, es importante elegir dónde añadirlo. 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 enlazada simple, solo puedes añadir nodos después de otros nodos, porque no tienes una referencia de nodo Previous al que referirte. En una lista doblemente enlazada, 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 que le sigue. Lo hace de la siguiente manera:

• Establece la referencia Next del CurrentNode a NewNode.

• Establece la referencia Next de NewNode al NextNode. Si no hay nextNode (como en el final de una lista), la función solo establece newNode como el siguiente nodo.

En una lista doblemente enlazada, tienes la opción de 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 enlazada simple, excepto 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, hay que borrar cualquier referencia a ese nodo y mantener, a la vez, el orden de la lista. Para ello, si el nodo que deseas eliminar tiene algún nodo después, debes enlazar los nodos anteriores al nodo eliminado con los nodos posteriores. En una lista enlazada simple, al no tener una referencia Previous, solo se pueden eliminar nodos posteriores al 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 desde el nodo inicial. En esta situación, necesitas establecer el nodo después del nodo inicial como el nuevo nodo inicial, o de lo contrario, tu lista enlazada no tendrá un lugar desde el que empezar.

Al igual que ocurre con la adición de nodos, la eliminación de nodos en una lista doblemente enlazada puede dividirse en la eliminación del 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, se muestra el código completo para cada uno de las clases 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 enlazadas, por lo que deberías explorar diferentes maneras de añadir funcionalidad. A continuación, se indican un par de formas con las que podrías mejorar tus listas enlazadas:

• ¿Y si cada lista almacenara también una referencia al nodo final?

• ¿Puedes implementar un método ToString() para imprimir el contenido de tus nodos?

• ¿Y si se invierte una lista? ¿Puedes implementar una funcionalidad Length()?

• ¿Puedes añadir más métodos al iterador para realizar nuevas operaciones?