Lista duplamente vinculada - Doubly linked list
Na ciência da computação , uma lista duplamente vinculada é uma estrutura de dados vinculada que consiste em um conjunto de registros vinculados sequencialmente chamados de nós . Cada nó contém três campos : dois campos de link ( referências ao nó anterior e ao próximo na sequência de nós) e um campo de dados. Os links anterior e seguinte dos nós inicial e final , respectivamente, apontam para algum tipo de terminador, normalmente um nó sentinela ou nulo , para facilitar o percurso da lista. Se houver apenas um nó sentinela, a lista será ligada circularmente por meio do nó sentinela. Pode ser conceituado como duas listas unidas formadas a partir dos mesmos itens de dados, mas em ordens sequenciais opostas.
Os dois links de nó permitem a travessia da lista em qualquer direção. Embora adicionar ou remover um nó em uma lista duplamente ligada exija a alteração de mais links do que as mesmas operações em uma lista ligada individualmente, as operações são mais simples e potencialmente mais eficientes (para nós que não sejam os primeiros nós) porque não há necessidade de monitorar o nó anterior durante a travessia ou não há necessidade de percorrer a lista para encontrar o nó anterior, para que seu link possa ser modificado.
Nomenclatura e implementação
O primeiro e o último nós de uma lista duplamente vinculada são imediatamente acessíveis (ou seja, acessíveis sem travessia e geralmente chamados de cabeça e cauda ) e, portanto, permitem percorrer a lista desde o início ou fim da lista, respectivamente: por exemplo, percorrer a lista do início ao fim, ou do fim ao início, em uma busca na lista de um nó com valor de dados específico. Qualquer nó de uma lista duplamente ligada, uma vez obtido, pode ser usado para iniciar um novo percurso da lista, em qualquer direção (para o início ou fim), a partir de um determinado nó.
Os campos de link de um nó de lista duplamente vinculado são freqüentemente chamados de próximo e anterior ou para frente e para trás . As referências armazenadas nos campos de link são geralmente implementadas como ponteiros , mas (como em qualquer estrutura de dados vinculada) também podem ser deslocamentos de endereço ou índices em uma matriz onde os nós residem.
Algoritmos básicos
Considere os seguintes algoritmos básicos escritos em Ada:
Abrir listas duplamente vinculadas
record DoublyLinkedNode {
next // A reference to the next node
prev // A reference to the previous node
data // Data or a reference to data
}
record DoublyLinkedList {
DoublyLinkedNode firstNode // points to first node of list
DoublyLinkedNode lastNode // points to last node of list
}
Percorrendo a lista
A passagem de uma lista duplamente vinculada pode ser em qualquer direção. Na verdade, a direção do percurso pode mudar muitas vezes, se desejado. Traversal é freqüentemente chamado de iteração , mas essa escolha de terminologia é lamentável, pois iteração tem uma semântica bem definida (por exemplo, em matemática) que não é análoga a traversal .
Para a frente
node := list.firstNode
while node ≠ null
<do something with node.data>
node := node.next
Para trás
node := list.lastNode
while node ≠ null
<do something with node.data>
node := node.prev
Inserindo um nó
Essas funções simétricas inserem um nó depois ou antes de um determinado nó:
function insertAfter(List list, Node node, Node newNode)
newNode.prev := node
if node.next == null
newNode.next := null -- (not always necessary)
list.lastNode := newNode
else
newNode.next := node.next
node.next.prev := newNode
node.next := newNode
function insertBefore(List list, Node node, Node newNode)
newNode.next := node
if node.prev == null
newNode.prev := null -- (not always necessary)
list.firstNode := newNode
else
newNode.prev := node.prev
node.prev.next := newNode
node.prev := newNode
Também precisamos de uma função para inserir um nó no início de uma lista possivelmente vazia:
function insertBeginning(List list, Node newNode)
if list.firstNode == null
list.firstNode := newNode
list.lastNode := newNode
newNode.prev := null
newNode.next := null
else
insertBefore(list, list.firstNode, newNode)
Uma função simétrica é inserida no final:
function insertEnd(List list, Node newNode)
if list.lastNode == null
insertBeginning(list, newNode)
else
insertAfter(list, list.lastNode, newNode)
Removendo um nó
A remoção de um nó é mais fácil do que a inserção, mas requer tratamento especial se o nó a ser removido for o firstNode ou o lastNode :
function remove(List list, Node node)
if node.prev == null
list.firstNode := node.next
else
node.prev.next := node.next
if node.next == null
list.lastNode := node.prev
else
node.next.prev := node.prev
Uma consequência sutil do procedimento acima é que a exclusão do último nó de uma lista define firstNode e lastNode como nulo e, portanto, trata a remoção do último nó de uma lista de um elemento corretamente. Observe que também não precisamos dos métodos "removeBefore" ou "removeAfter" separados, porque em uma lista duplamente vinculada podemos apenas usar "remove (node.prev)" ou "remove (node.next)" onde eles são válidos. Isso também pressupõe que o nó que está sendo removido tem a garantia de existência. Se o nó não existir nesta lista, será necessário algum tratamento de erros.
Listas circulares duplamente vinculadas
Percorrendo a lista
Supondo que someNode seja algum nó em uma lista não vazia, este código percorre essa lista começando com someNode (qualquer nó servirá):
Para a frente
node := someNode
do
do something with node.value
node := node.next
while node ≠ someNode
Para trás
node := someNode
do
do something with node.value
node := node.prev
while node ≠ someNode
Observe o adiamento do teste para o final do loop. Isso é importante para o caso em que a lista contém apenas o nó someNode .
Inserindo um nó
Esta função simples insere um nó em uma lista duplamente ligada circularmente após um determinado elemento:
function insertAfter(Node node, Node newNode)
newNode.next := node.next
newNode.prev := node
node.next.prev := newNode
node.next := newNode
Para fazer um "insertBefore", podemos simplesmente "insertAfter (node.prev, newNode)".
Inserir um elemento em uma lista possivelmente vazia requer uma função especial:
function insertEnd(List list, Node node)
if list.lastNode == null
node.prev := node
node.next := node
else
insertAfter(list.lastNode, node)
list.lastNode := node
Para inserir no início, simplesmente "insertAfter (list.lastNode, node)".
Finalmente, a remoção de um nó deve lidar com o caso em que a lista se esvazia:
function remove(List list, Node node);
if node.next == node
list.lastNode := null
else
node.next.prev := node.prev
node.prev.next := node.next
if node == list.lastNode
list.lastNode := node.prev;
destroy node
Excluindo um nó
Como em listas duplamente vinculadas, "removeAfter" e "removeBefore" podem ser implementados com "remove (list, node.prev)" e "remove (list, node.next)".
Conceitos avançados
Lista duplamente ligada assimétrica
Uma lista duplamente vinculada assimétrica está em algum lugar entre a lista vinculada simples e a lista duplamente vinculada regular. Ele compartilha alguns recursos com a lista unicamente vinculada (passagem em uma única direção) e outros da lista duplamente vinculada (facilidade de modificação)
É uma lista em que o link anterior de cada nó aponta não para o nó anterior, mas para o link para si mesmo. Embora isso faça pouca diferença entre os nós (apenas aponta para um deslocamento dentro do nó anterior), ele muda o cabeçalho da lista: permite que o primeiro nó modifique o link firstNode facilmente.
Enquanto um nó estiver em uma lista, seu link anterior nunca será nulo.
Inserindo um nó
Para inserir um nó antes de outro, alteramos o link que apontava para o nó antigo, usando o link anterior ; em seguida, defina o próximo link do novo nó para apontar para o nó antigo e altere o link anterior desse nó de acordo.
function insertBefore(Node node, Node newNode)
if node.prev == null
error "The node is not in a list"
newNode.prev := node.prev
atAddress(newNode.prev) := newNode
newNode.next := node
node.prev = addressOf(newNode.next)
function insertAfter(Node node, Node newNode)
newNode.next := node.next
if newNode.next != null
newNode.next.prev = addressOf(newNode.next)
node.next := newNode
newNode.prev := addressOf(node.next)
Excluindo um nó
Para remover um nó, simplesmente modificamos o link apontado por prev , independentemente de o nó ser o primeiro da lista.
function remove(Node node)
atAddress(node.prev) := node.next
if node.next != null
node.next.prev = node.prev
destroy node