Uma lista duplamente vinculada fornece a cada nó dois ponteiros — next e prev — para que você possa percorrer em ambas as direções e deletar um nó em O(1) quando já tem uma referência a ele (não há necessidade de caminhar da cabeça para encontrar o antecessor).
null <- [10] <-> [20] <-> [30] -> null
prev/next links in BOTH directions
class Node:
def __init__(self, val):
self.val, self.prev, self.next = val, None, None
def remove(node): # O(1) — no traversal needed
if node.prev: node.prev.next = node.next
if node.next: node.next.prev = node.prev
Em uma lista simplesmente vinculada, deletar um nó requer primeiro encontrar seu antecessor → O(n).
| Aspecto | Simplesmente | Duplamente |
|---|---|---|
| Ponteiros por nó | 1 (next) | 2 (next, prev) |
| Percorrer para trás | não | sim |
| Deletar nó conhecido | O(n) | O(1) |
| Overhead de memória | menor | maior |
O splice-out O(1) de um nó conhecido é a propriedade-chave que torna listas duplamente vinculadas parceiras de mapas hash em um cache LRU.
O ponteiro extra prev negocia memória pela flexibilidade de movimento bidirecional e exclusão em tempo constante.