Listas enlazadas en Verse | Unreal Editor para Fortnite Desarrllador

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.

Resumen

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 llama nodo. Un nodo es un contenedor que tiene datos y una referencia al siguiente nodo. texto alternativo de la imagen

La unión de diferentes nodos en una secuencia crea una lista enlazada. El primer nodo de la 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:

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 } # 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 } # 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 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.

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.

# 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, 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.

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.

# Crea una lista enlazada con el nodo1 como inicial.
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:

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("Starting at the Head Node...")
        # Si el nodo actual tiene un nodo siguiente, establece el nodo actual
        # al siguiente nodo de la lista
        loop:
            if(NextNode := CurrentNode?.Next?):
                set CurrentNode = option{NextNode}
                set NodeNumber += 1
                Print("Traveling to Node {NodeNumber}!")
            else:
                Print("No next node, this is the Tail node!")
                break

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.

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 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:

doubly_linked_list := class():
    Head:doubly_linked_node

    # Recorre una LinkedList, ¡pero tanto hacia adelante como hacia atrás!
    TraverseDoublyLinkedList():void=
        var CurrentNode:?doubly_linked_node := option{Head}
        var NodeNumber:int = 1
        Print("Starting at the Head Node, and going forward...")
        loop:
            if(NextNode := CurrentNode?.Next?):
                set CurrentNode = option{NextNode}
                set NodeNumber += 1
                Print("Traveling to Node {NodeNumber}!")
            else:
                Print("No next node, this is the Tail node!")
                break
        Print("Now let's go backward to the Head node...")
        loop:
            if(PreviousNode := CurrentNode?.Previous?):
                set CurrentNode = option{PreviousNode}
                set NodeNumber -= 1
                Print("Traveling to Node {NodeNumber}!")
            else:
                Print("No previous Node, we're back at the Head node!")
                break

doubly_linked_list := class():
    Head:doubly_linked_node

# Recorre una LinkedList, ¡pero tanto hacia adelante como hacia atrás!
    TraverseDoublyLinkedList():void=
        var CurrentNode:?doubly_linked_node := option{Head}
        var NodeNumber:int = 1
        Print("Starting at the Head Node, and going forward...")
        loop:
            if(NextNode := CurrentNode?.Next?):
                set CurrentNode = option{NextNode}
                set NodeNumber += 1
                Print("Traveling to Node {NodeNumber}!")
            else:
                Print("No next node, this is the Tail node!")
                break
        Print("Now let's go backward to the Head node...")
        loop:
            if(PreviousNode := CurrentNode?.Previous?):
                set CurrentNode = option{PreviousNode}
                set NodeNumber -= 1
                Print("Traveling to Node {NodeNumber}!")
            else:
                Print("No previous Node, we're back at the Head node!")
                break

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.

linked_list_iterator := class:
    List:linked_list
    var CurrentNode:list_node

    # Si hay un NextNode para que el iterador se desplace, se desplaza a ese nodo
    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 aquí Next() incluye los especificadores <transacts> y <decides>. La función debe ser <transacts> ya que actualiza la var CurrentNode y quieres poder incluir <decides> , ya que al hacer falible a Next(), podrás saber si iteraste al nodo siguiente 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
    # La línea de abajo fallará porque no puedes acceder a Lista 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 permite acceder al valor de Lista y asignar CurrentNode a su nodo inicial.

# Construye un Iterador con CurrentNode como nodo ficticio antes del inicial de la lista dada.
MakeIterator<constructor>(List:linked_list) := linked_list_iterator:
    List := List
    # Puedes acceder a Lista desde este ámbito en una función constructora
    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 doblemente enlazada es muy similar, salvo que se inicializa mediante nodos doblemente enlazados.

# Construye un Iterador con CurrentNode como nodo ficticio antes del inicial de la lista dada.
MakeDoublyLinkedIterator<constructor>(List:doubly_linked_list) := doubly_linked_list_iterator:
    List := List
    # Puedes acceder a Lista desde este ámbito en una función constructora
    CurrentNode:= doubly_linked_node{Next := option{List.Head}}

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.

# Si hay un NextNode para que el iterador se desplace, se desplaza a ese nodo
Next()<transacts><decides>:doubly_linked_node=
    set CurrentNode = CurrentNode.Next?

# Si hay un PreviousNode para que el iterador se desplace, se desplaza a ese nodo
Previous()<transacts><decides>:doubly_linked_node=
    set CurrentNode = CurrentNode.Previous?

Cómo agregar 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.

# 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("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.

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("Successfully added a new node!")
    else:
        set CurrentNode.Next = option{NewNode}
        Print("Successfully added a new node to the tail of the list!")

# 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("Successfully added a new node!")
    else:
        set NewNode.Next = option{CurrentNode}
        set CurrentNode.Previous = option{NewNode}
        Print("Successfully added a new node to the tail of the list!")

# 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("Successfully added a new node!")
    else:
        set CurrentNode.Next = option{NewNode}
        Print("Successfully added a new node to the tail of the list!")

# 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("Successfully added a new node!")
    else:
        set NewNode.Next = option{CurrentNode}
        set CurrentNode.Previous = option{NewNode}
        Print("Successfully added a new node to the tail of the list!")

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.

# Elimina el siguiente nodo después de CurrentNode. Si el siguiente nodo
# tiene una referencia Next, establece ese nodo como 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("Removed the node between CurrentNode and the node after it")
            # Si el nodo eliminado es el nodo inicial, establece el siguiente nodo como nuevo inicial
            if(RemovedNode = List.Head):
                Print("Removed node was the head node, setting the node after as the new head")
                set List.Head = NodeAfter
        else:
            set CurrentNode.Next = false
            Print("Removed the node before CurrentNode")
    else:
        Print("Couldn't remove the node")

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.

# 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("Removed the node between CurrentNode and the node after it")
            # Si el nodo eliminado es el nodo inicial, establece el siguiente nodo como nuevo inicial
            if(RemovedNode = List.Head):
                Print("Removed node was the head node, setting the node after as the new head")
                set List.Head = NodeAfter
                # No es conveniente poder volver al nodo ficticio
                # así que establece el nodo previo al nuevo inicial como falso
                set NodeAfter.Previous = false       
        else:
            set CurrentNode.Next = false
            Print("Removed the node after CurrentNode")
    else:
        Print("Couldn't remove the node")   

# 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("Removed the node between CurrentNode and the node before it")
            # Si el nodo eliminado es el nodo inicial, establece el siguiente nodo como nuevo inicial
        else:
            set CurrentNode.Previous = false
            if(RemovedNode = List.Head):
                Print("Removed node was the head node, setting the node after as the new head")
                set List.Head = CurrentNode
            Print("Removed the node after CurrentNode")
    else:
        Print("Couldn't remove the node")

# 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("Removed the node between CurrentNode and the node after it")
            # Si el nodo eliminado es el nodo inicial, establece el siguiente nodo como nuevo inicial
            if(RemovedNode = List.Head):
                Print("Removed node was the head node, setting the node after as the new head")
                set List.Head = NodeAfter
                # No es conveniente poder volver al nodo ficticio
                # así que establece el nodo previo al nuevo inicial como falso
                set NodeAfter.Previous = false       
        else:
            set CurrentNode.Next = false
            Print("Removed the node after CurrentNode")
    else:
        Print("Couldn't remove the node")

# 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("Removed the node between CurrentNode and the node before it")
            # Si el nodo eliminado es el nodo inicial, establece el siguiente nodo como nuevo inicial
        else:
            set CurrentNode.Previous = false
            if(RemovedNode = List.Head):
                Print("Removed node was the head node, setting the node after as the new head")
                set List.Head = CurrentNode
            Print("Removed the node after CurrentNode")
    else:
        Print("Couldn't remove the node")

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?