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. Os elementos em uma lista vinculada são chamados de nós. Um nó é um contêiner que inclui 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ó da lista é chamado de nó inicial, e o último nó é chamado de nó final. 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 no 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:
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ó final de uma lista vinculada). Se quiser alterar a vinculação da lista dinamicamente, Next precisa ser var. O nó também contém um 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!
~~~(verse) Node1 := list_node{ Next := false, Data := 1 } # Um integer Node2 := list_node{ Next := false, Data := "String" } # Uma string Node3 := list_node{ Next := false, Data := []int} # Uma matriz Node4 := list_node{ Next := false, Data := list_node } # Classe "list_node" Node5 := list_node{ Next := false, Data := Node1 } # O primeiro nó
O especificador `<unique>`permite que `list_node` seja [comparável](comparable-in-verse). Permitindo 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ê pode comparar o valor em `Data` com outro valor para encontrar um nó específico.
### Listas vinculadas isoladamente
O tipo mais básico de lista vinculada é uma **lista vinculada isoladamente**, em que cada nó contém uma referência ao próximo nó (um único link). Para transformar nós em uma lista, vincule-os usando as referências `Next` em cada nó.
~~~(verse)
# Vincular cada nó ao próximo nó da lista
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.
~~~(verse) linked_list := class: var Head:list_node
Uma classe `linked_list` básica contém apenas uma referência ao nó inicial. Para criar uma instância da sua classe `linked_list`, vincule seus nós juntos e, em seguida, instancie sua lista usando o nó inicial.
~~~(verse)
# Criar uma lista vinculada com "Node1" como o nó inicial.
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:
~~~(verse) linked_list := class: var Head:list_node
TraverseList():void= var CurrentNode:?list_node := option{Head} # O nó em que você está atualmente var NodeNumber:int = 1 # O número do nó atual Print("Iniciando no nó inicial...") # Se o nó atual tiver um próximo nó, defina o nó atual como # o próximo nó da lista loop: if(NextNode := CurrentNode?.Next?): set CurrentNode = option{NextNode} set NodeNumber += 1 Print("Indo para o nó {NodeNumber}!") else: Print("Não há um próximo nó, este é o nó final!") break
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 vinculadas duplamente
Ao contrário das listas vinculadas isoladamente, os nós em uma **lista vinculada duplamente** também contêm uma referência ao nó que veio antes dele, chamado de nó **anterior**.
~~~(verse)
doubly_linked_node := class<unique>:
var Next:?doubly_linked_node = false
var Previous:?doubly_linked_node = false
Data:any = {}
~~~
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:
~~~(verse)
doubly_linked_list := class():
Head:doubly_linked_node
# Cruze uma lista vinculada, mas para trás e para frente!
TraverseDoublyLinkedList():void=
var CurrentNode:?doubly_linked_node := option{Head}
var NodeNumber:int = 1
Print("Iniciando no nó inicial e seguindo em frente...")
loop:
if(NextNode := CurrentNode?.Next?):
set CurrentNode = option{NextNode}
set NodeNumber += 1
Print("Indo para o nó {NodeNumber}!")
else:
Print("Não há um próximo nó, este é o nó final!")
break
Print("Agora vamos voltar para o nó inicial...")
loop:
if(PreviousNode := CurrentNode?.Previous?):
set CurrentNode = option{PreviousNode}
set NodeNumber -= 1
Print("Indo para o nó {NodeNumber}!")
else:
Print("Nenhum nó anterior, voltamos ao nó inicial!")
break
Listas vinculadas circulares
Em uma lista vinculada 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.
linked_list_iterator := class:
List:linked_list
var CurrentNode:list_node
# Se houver um NextNode para o iterador acessar, deslocar-se para esse nó
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>`, já que atualiza a `var` de `CurrentNode`, e você deseja incluir `<decides>`, já que tornar `Next()` falível permite saber se a iteração para o próximo nó ocorreu.
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` para um nó fictício com 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.
~~~(verse)
linked_list_iterator := class:
List:linked_list
# A linha abaixo falhará, porque você não pode acessar a lista a partir desse escopo
var CurrentNode:list_node := list_node{Next := option{List.Head}}
~~~
Em vez disso, para instanciar um iterador, você pode usar uma função de [construtor](constructor-in-verse). Um construtor é um tipo composto que cria uma instância da classe à qual está associado. O construtor define valores iniciais para um objeto e permite que você acesse o valor da Lista e atribua `CurrentNode` ao seu nó inicial.
~~~(verse)
# Crie um iterador com CurrentNode como um nó fictício antes do início da lista especificada.
MakeIterator<constructor>(List:linked_list) := linked_list_iterator:
List := List
# Você pode acessar a lista a partir desse escopo em uma função de constructor
CurrentNode:= list_node{Next := option{List.Head}}
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.
~~~(verse)
# Crie um iterador com CurrentNode como um nó fictício antes do início da lista especificada.
MakeDoublyLinkedIterator<constructor>(List:doubly_linked_list) := doubly_linked_list_iterator:
List := List
# Você pode acessar a lista a partir desse escopo em uma função de constructor
CurrentNode:= doubly_linked_node{Next := option{List.Head}}
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 vinculadas isoladamente 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.
~~~(verse)
# Se houver um NextNode para o iterador acessar, deslocar-se para esse nó
Next()<transacts><decides>:doubly_linked_node=
set CurrentNode = CurrentNode.Next?
# Se houver um PreviousNode para onde o iterador se deslocar, deslocar-se até esse nó
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 vinculada isoladamente, você só pode adicionar nós após outros nós, porque não tem uma referência de um nó `Previous` (anterior) na qual se basear. Em uma lista vinculada duplamente, é possível adicionar nós antes ou depois de outros nós.
~~~(verse)
# Adicionar um novo nó depois de CurrentNode
AddNextNode(NewNode:list_node):void=
if(NextNode := CurrentNode.Next?):
set NewNode.Next = option{NextNode}
set CurrentNode.Next = option{NewNode}
Print("Novo nó adicionado com êxito!")
else:
set CurrentNode.Next = option{NewNode}
Print("Novo nó adicionado com êxito ao final da lista!")
~~~
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` de `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ó.
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.
~~~(verse)
# Adicionar um novo nó depois 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("Novo nó adicionado com êxito!")
else:
set CurrentNode.Next = option{NewNode}
Print("Novo nó adicionado com êxito ao final da lista!")
# Adicionar um novo nó 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("Novo nó adicionado com êxito!")
else:
set NewNode.Next = option{CurrentNode}
set CurrentNode.Previous = option{NewNode}
Print("Novo nó adicionado com êxito ao final da lista!")
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 vinculada isoladamente, como você não tem uma referência Previous (anterior), só pode remover nós após CurrentNode.
~~~(verse)
Remover o próximo nó após CurrentNode. Se o próximo nó
tiver uma referência Next, definir esse nó como o próximo nó de CurrentNode
RemoveNextNode():void= if(RemovedNode := CurrentNode.Next?): if(NodeAfter := RemovedNode.Next?, set RemovedNode.Next = false): set CurrentNode.Next = option{NodeAfter} Print("Nó removido entre CurrentNode e o nó depois dele") # Se o nó removido for o nó inicial, definir o próximo nó como o novo inicial if(RemovedNode = List.Head): Print("O nó removido era o nó inicial, definindo o nó seguinte como o novo inicial") set List.Head = NodeAfter else: set CurrentNode.Next = false Print("Nó removido antes de CurrentNode") else: Print("Não foi possível remover o nó") ~~~
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.
~~~(verse)
Como remover o nó após 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("Nó removido entre CurrentNode e o nó depois dele")
# Se o nó removido for o nó inicial, definir o próximo nó como o novo inicial
if(RemovedNode = List.Head):
Print("O nó removido era o nó inicial, definindo o nó seguinte como o novo inicial")
set List.Head = NodeAfter
# Como você não quer que seja possível voltar para o nó fictício,
# defina Previous do novo nó inicial como falso
set NodeAfter.Previous = false
else:
set CurrentNode.Next = false
Print("Nó removido após CurrentNode")
else:
Print("Não foi possível remover o nó")
Remover o nó 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("Nó removido entre CurrentNode e o nó antes dele") # Se o nó removido for o nó inicial, definir o próximo nó como o novo inicial else: set CurrentNode.Previous = false if(RemovedNode = List.Head): Print("O nó removido era o nó inicial, definindo o nó seguinte como o novo inicial") set List.Head = CurrentNode Print("Nó removido após CurrentNode") else: Print("Não foi possível remover o nó") ~~~
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 lista também armazenasse uma referência ao nó final?
-
Você pode implementar um método
ToString()para gerar o conteúdo dos nós? -
Que tal inverter uma lista? Você pode implementar uma funcionalidade
Length()? -
Você pode adicionar mais métodos ao iterador para fazer novas operações?