Una lista doppiamente collegata assegna a ogni nodo due puntatori — next e prev — così puoi attraversarla in entrambe le direzioni e cancellare un nodo in O(1) quando già possiedi un riferimento ad esso (non è necessario camminare dalla testa per trovare il predecessore).
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
In una lista singolarmente collegata, cancellare un nodo richiede di trovare prima il suo predecessore → O(n).
| Aspetto | Singolarmente | Doppiamente |
|---|---|---|
| Puntatori per nodo | 1 (next) | 2 (next, prev) |
| Attraversamento all'indietro | no | sì |
| Cancella nodo noto | O(n) | O(1) |
| Overhead di memoria | inferiore | superiore |
L'O(1) splice-out di un nodo noto è la proprietà chiave che rende le liste doppiamente collegate il partner di mappe hash in una cache LRU.
Il puntatore prev aggiuntivo scambia memoria per la flessibilità del movimento bidirezionale e della cancellazione a tempo costante.
Una raccolta di domande di colloquio IT con risposte dettagliate — da Junior a Senior.
Dona