Lista Duplamente Ligada (Doubly Linked List)
Na ciência da computação, uma lista duplamente conectada é uma estrutura de dados vinculada que se consistem em um conjunto de registros sequencialmente vinculados chamados de nós (nodes). Em cada nó contém dois campos, chamados de ligações, que são referenciados ao nó anterior e posterior de uma sequência de nós. O começo e o fim dos nós anteriormente e posteriormente ligados, respectiviamente, apontam para algum tipo de terminação, normalmente um nó sentinela ou nulo, para facilitar a travessia da lista. Se existe somente um nó sentinela, então a lista é ligada circularmente através do nó sentinela. Ela pode ser conceitualizada como duas listas individualmente ligadas e formadas a partir dos mesmos itens, mas em ordem sequencial opostas.
Made with okso.app
Os dois nós ligados permitem a travessia da lista em qualquer direção. Enquanto adicionar ou remover um nó de uma lista duplamente vinculada requer alterar mais ligações (conexões) do que em uma lista encadeada individualmente (singly linked list), as operações são mais simples e potencialmente mais eficientes (para nós que não sejam nós iniciais) porque não há necessidade de manter um rastreamento do nó anterior durante a travessia ou não há necessidade de percorrer a lista para encontrar o nó anterior, para que então sua ligação/conexão possa ser modificada.
Pseudocódigo para Operações Básicas
Inserir
Add(value)
Pre: value is the value to add to the list
Post: value has been placed at the tail of the list
n ← node(value)
if head = ø
head ← n
tail ← n
else
n.previous ← tail
tail.next ← n
tail ← n
end if
end Add
Remoção
Remove(head, value)
Pre: head is the head node in the list
value is the value to remove from the list
Post: value is removed from the list, true; otherwise false
if head = ø
return false
end if
if value = head.value
if head = tail
head ← ø
tail ← ø
else
head ← head.next
head.previous ← ø
end if
return true
end if
n ← head.next
while n = ø and value !== n.value
n ← n.next
end while
if n = tail
tail ← tail.previous
tail.next ← ø
return true
else if n = ø
n.previous.next ← n.next
n.next.previous ← n.previous
return true
end if
return false
end Remove
Travessia reversa
ReverseTraversal(tail)
Pre: tail is the node of the list to traverse
Post: the list has been traversed in reverse order
n ← tail
while n = ø
yield n.value
n ← n.previous
end while
end Reverse Traversal
Complexidades
Complexidade de Tempo
| Acesso | Pesquisa | Inserção | Remoção |
|---|---|---|---|
| O(n) | O(n) | O(1) | O(n) |
Complexidade de Espaço
O(n)