Listas vinculadas

As listas vinculadas são uma estrutura de dados comum na ciência da computação. Você pode usar uma lista vinculada para representar uma lista de reprodução de música ou o histórico de rastreamento de ações, por exemplo.

Visão geral

Uma lista vinculada é uma estrutura de dados linear em que cada elemento armazena uma referência ao próximo elemento na lista. Cada elemento em uma lista vinculada é chamado de nó. Um nó é um contêiner que armazena alguns dados e uma referência ao próximo nó.

Vincular nós diferentes em uma sequência cria uma lista vinculada. O primeiro nó na lista é chamado de nó inicial (head), e o último nó é chamado de nó final (tail). Para percorrer a lista, você começa no início e se desloca até o próximo elemento usando a referência em cada nó.

Quando usar

As listas vinculadas são um bom ponto de partida para implementar outras estruturas de dados, como pilhas ou filas. Também são uma maneira direta de armazenar dados para o acesso sequencial e oferecem suporte para a rápida inserção de novos elementos. Ao contrário de matrizes, as listas vinculadas não ficam contíguas (uma ao lado da outra) na memória. O que significa que um nó pode estar em qualquer lugar na memória, e a referência ao próximo nó informa a localização. Para inserir ou excluir nós de uma lista vinculada, tudo o que você precisa fazer é alterar as referências ao nó que vem a seguir.

Quando não usar

Se o seu programa requer acesso aleatório a elementos (como escolher um jogador aleatório de uma lista), as listas vinculadas não possuem essa funcionalidade. As listas vinculadas são menos eficientes que matrizes quando você precisa acessar um nó específico no meio da lista, pois terá que começar do início e percorrer até o nó específico necessário.

Implementação em Verse

A API Verse não tem uma implementação integrada de listas vinculadas, mas você mesmo pode criar uma.

As listas vinculadas são formadas por nós e você precisará definir uma classe para representá-las. Um exemplo de um tipo genérico de nó é mostrado abaixo:

# 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 = {}

Aqui, a variável de opção Next armazena uma referência ao próximo nó na lista, que é do tipo list_node. Observe que Next deve ser uma variável option, porque um nó pode nem sempre ter um nó seguinte para o qual apontar (como o nó tail de uma lista vinculada). Se quiser alterar a vinculação da lista dinamicamente, Next precisa ser uma var. O nó também contém algum valor, que é armazenado em Data. Como esse é um tipo genérico de nó, Data é do tipo any e o nó pode conter qualquer tipo de dado. Pode ser um tipo comum, um contêiner ou até mesmo outra 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

O especificador <unique> permite que list_node seja comparable. O que permite que você verifique se um nó é igual a algum outro nó, por exemplo, verificar se o nó é o início ou o fim de uma lista.

Se precisar de uma implementação mais específica, como um nó que lida apenas com números ou strings, certifique-se de alterar o tipo de Data para corresponder. Se Data for do tipo comparable, você poderá comparar o valor em Data com outro valor para encontrar um nó 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 com vinculação simples

O tipo mais básico de lista vinculada é uma lista com vinculação simples, em que cada nó contém uma referência ao próximo nó (uma única vinculação). Para transformar seus nós em uma lista, vincule-os usando as referências Next em cada nó.

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

Embora os nós estejam vinculados, convém definir a lista vinculada em uma classe. Isso facilitará a execução de funções usando essa lista, em vez de fazer referência ao seu primeiro nó todas as vezes.

# 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

Uma classe básica de linked_list contém apenas uma referência ao nó inicial. Para criar uma instância da sua classe linked_list, vincule seus nós e, em seguida, instanciar sua lista usando o nó inicial.

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

Para cruzar a lista, você começa no nó inicial e percorre a lista, parando no final. Você pode fazer isso em uma função externa ou em uma função de classe dentro da classe linked_list. Um exemplo de função que cruza toda a lista do início ao fim é fornecido abaixo:

# 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

Aqui, a função TraverseList() verifica se CurrentNode contém uma referência Next e a armazena em NextNode. Nesse caso, ela define CurrentNode como NextNode repetidamente até chegar ao nó final. Como o nó final não tem uma referência Next, o loop para aqui.

Listas com vinculação dupla

Ao contrário das listas com vinculação simples, os nós em uma lista com vinculação dupla também contêm uma referência ao nó que veio antes dele, chamado de nó 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 = {}

Assim como em nós com vinculação simples, se você precisar de uma implementação mais específica que lide apenas com determinados tipos de dados, certifique-se de alterar o tipo de Data para corresponder.

# 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

Significa que você pode percorrer os nós em uma lista vinculada duplamente para frente e para trás. O que pode ser feito em uma função externa ou em uma função de classe. Um exemplo de função que cruza a lista do início ao fim, e vice-versa, é fornecido abaixo:

# 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 com vinculação circular

Em uma lista com vinculação circular, o nó inicial está vinculado ao nó final. Ou seja, você pode percorrer toda a lista além do nó final e voltar ao inicial. A lista vinculada circular pode ser vinculada isoladamente ou duplamente. O único requisito é que o nó inicial esteja vinculado ao nó final, ou vice-versa.

Iteradores

Um iterador é um objeto que permite iterar sobre um contêiner e executar operações ao longo do caminho. Você pode pensar nisso como um vagão de trem cheio de passageiros. O trem percorre um trilho, parando em cada estação ao longo do caminho. Em cada estação, o trem realiza uma tarefa, como permitir o embarque ou desembarque de passageiros. Com relação às listas vinculadas, cada estação é um nó na lista. O trem (iterador) percorre a lista para cada nó e pode executar operações onde parar.

Iteradores são úteis para listas vinculadas porque permitem que você execute operações em locais específicos, em vez de apenas no nó inicial ou 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?

Aqui, o iterador contém uma referência à lista sobre a qual itera e um CurrentNode no qual o iterador está atualmente parado. A função Next() verifica se CurrentNode tem um nó depois dele e, em seguida, pula para esse nó. Observe que Next() inclui os especificadores <transacts> e <decides>. A função deve ser <transacts> pois atualiza a var CurrentNode, e é importante incluir <decides>, pois tornar Next() falível permite saber se a iteração para o próximo nó ocorreu ou não.

Embora possa parecer que um iterador deva começar no início de uma lista, na verdade, ele precisa começar antes do início. Isso é feito para que o iterador possa realizar operações no nó inicial, como inserir nós antes do nó inicial ou excluir totalmente esse nó inicial.

Para inicializar o iterador antes do nó inicial, você pode inicializar CurrentNode em um nó fictício que tem o nó inicial da lista como o próximo nó. Em Verse, não é possível acessar List ao inicializar CurrentNode, porque a variável de membros de classe não pode ser acessada no mesmo escopo, apenas em escopos diferentes, como dentro de uma função.

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

Em vez disso, para instanciar um iterador, você pode usar uma função constructor. Um construtor é um tipo composto que cria uma instância da classe à qual está associado. A função constructor define valores iniciais para um objeto e permite acessar o valor de List e atribuir CurrentNode ao seu nó 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

A inicialização de um iterador para uma lista vinculada duplamente é um processo muito semelhante, exceto pelo fato de você inicializá-lo usando nós vinculados duplamente.

# 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

Como iterar entre nós

Você pode mover o iterador para frente ou para trás, dependendo da vinculação da sua lista. Os iteradores em uma lista vinculada isoladamente só podem ir para frente, enquanto os iteradores em uma lista vinculada duplamente podem se deslocar em qualquer direção. Essa funcionalidade é definida em duas funções, Next() e Previous(). Lembre-se de que listas com vinculação simples não terão uma função Previous(). Listas vinculadas circularmente podem ter qualquer função, o que depende se são vinculadas isolada ou duplamente.

# 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?

Como adicionar nós

Você pode usar iteradores para adicionar nós a locais específicos na lista vinculada. Ao adicionar um nó, é importante escolher onde adicioná-lo. Você pode adicionar esse nó antes ou depois do nó atual, mas isso depende da estrutura da lista. Em uma lista com vinculação simples, você só pode adicionar nós após outros nós, porque não existe uma referência de nó Previous (anterior) na qual se basear. Em uma lista vinculada duplamente, é possível adicionar nós antes ou depois de outros nós.

# 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!")

Aqui, a função AddNode adiciona um nó entre CurrentNode e o nó depois dele. Ela faz isso da seguinte maneira:

• Definindo a referência Next do CurrentNode como NewNode.

• Definindo a referência Next de NewNode como NextNode. Se não houver NextNode (como no final de uma lista), a função definirá apenas NewNode como o próximo nó.

Em uma lista com vinculação dupla, você tem a opção de adicionar nós antes ou depois de CurrentNode. Você pode dividir essa funcionalidade em duas funções: AddNodeAfter() e AddNodeBefore(). A implementação é muito semelhante à da lista com vinculação simples, com a diferença de que você também deve se lembrar de definir a referência Previous para cada nó.

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

Como remover nós

Para remover nós, você precisa excluir todas as referências a esse nó ao mesmo tempo em que preserva a ordem da lista. Para isso, se o nó que deseja remover tiver algum nó depois dele, será necessário vincular todos os nós antes do nó removido aos nós depois dele. Em uma lista com vinculação simples, como você não tem uma referência Previous, só pode remover nós após o 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")

Observe que você precisa de um caso especial ao remover do nó inicial. Nessa situação, é necessário definir o nó após o nó inicial como o novo nó inicial. Caso contrário, a lista vinculada não terá um ponto de partida.

Assim como ao adicionar nós, a remoção de nós em uma lista vinculada duplamente pode ser dividida na remoção do nó antes ou depois do nó atual.

# 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

Veja a seguir o código completo de cada uma das classes neste exemplo.

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 conta própria

Existem várias maneiras de aprimorar listas vinculadas, e você deve explorar diferentes maneiras de adicionar essa funcionalidade. A seguir estão algumas maneiras de aprimorar listas vinculadas:

• E se cada List também armazenasse uma referência ao nó final?

• É possível implementar um método ToString() para gerar o conteúdo dos nós?

• Que tal inverter uma lista? É possível implementar uma funcionalidade Length()?

• É possível adicionar mais métodos ao iterador para fazer novas operações?