Una lista doblemente enlazada le da a cada nodo dos punteros — next y prev — para que pueda recorrer en ambas direcciones y eliminar un nodo en O(1) cuando ya tiene una referencia al mismo (no necesita caminar desde el inicio para encontrar el predecesor).
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
En una lista simplemente enlazada, eliminar un nodo requiere encontrar primero su predecesor → O(n).
| Aspecto | Simplemente | Doblemente |
|---|---|---|
| Punteros por nodo | 1 (next) | 2 (next, prev) |
| Recorrer hacia atrás | no | sí |
| Eliminar nodo conocido | O(n) | O(1) |
| Sobrecarga de memoria | menor | mayor |
La eliminación O(1) de un nodo conocido es la propiedad clave que hace que las listas doblemente enlazadas sean la pareja de los mapas hash en un caché LRU.
El puntero adicional prev intercambia memoria por la flexibilidad del movimiento bidireccional y la eliminación en tiempo constante.
Una biblioteca de preguntas de entrevista de IT con respuestas detalladas — de Junior a Senior.
Donar