La lista enlazada simple que construimos en la lección anterior tiene una asimetría incómoda: cada nodo sabe quién viene después, pero ignora por completo quién viene antes. Esa ceguera nos obligó al baile de dos referencias (anterior y actual) para borrar, y hace directamente imposible recorrer la lista hacia atrás. En esta lección añadimos la flecha que falta: cada nodo llevará dos referencias, anterior y siguiente, y obtendremos la lista doblemente enlazada, con borrados e inserciones O(1) cuando ya tenemos el nodo en la mano y recorridos en ambos sentidos. El precio, como siempre, existe y lo pondremos en la balanza. Para TaskFlow, esta estructura es la pieza perfecta para un historial de tareas navegable: avanzar y retroceder por las tareas trabajadas, como el botón "atrás" y "adelante" de un navegador.

1. El nodo doble: dos flechas por nodo
2. Cabeza y cola: la estructura y sus invariantes
3. Insertar por ambos extremos
4. Insertar y borrar O(1) dado el nodo
5. Recorrer en ambos sentidos
6. Simple vs doble: la balanza completa
7. TaskFlow: el historial de tareas navegable
8. Un puente hacia collections.deque

La modificación es pequeña de escribir y grande de consecuencias:

Cada pareja de nodos vecinos está unida por dos flechas, una en cada sentido. De ahí se derivan las dos propiedades nuevas:

• Desde cualquier nodo se puede caminar hacia atrás (actual = actual.anterior), no solo hacia delante.
• Cualquier nodo conoce a su vecino previo sin buscarlo: el patrón del nodo anterior de 02-02 deja de ser necesario.

Y la servidumbre nueva: cada operación debe mantener coherentes el doble de flechas. Donde la lista simple recableaba 2 referencias, la doble recablea hasta 4. Ninguna operación cambia de clase de coste por ello (sigue siendo O(1) recablear), pero el código tiene más puntos donde equivocarse, y lo veremos.

En la lista simple, la cola era un truco opcional para abaratar insertar_al_final. Aquí es parte esencial del diseño: sin ella no habría por dónde empezar el recorrido hacia atrás. Conviene fijar por escrito los invariantes — las condiciones que todo método debe dejar ciertas al terminar:

• self.cabeza.anterior es siempre None (nadie precede al primero).
• self.cola.siguiente es siempre None (nadie sigue al último).
• Si la lista está vacía, cabeza y cola son ambas None; si tiene un elemento, ambas apuntan al mismo nodo.
• Para todo nodo interior n: n.siguiente.anterior is n y n.anterior.siguiente is n (las flechas de ida y vuelta se corresponden).

Cuando un método deja las flechas incoherentes, los síntomas aparecen lejos del culpable (un recorrido hacia atrás que se corta, un borrado que resucita nodos). Comprobar los invariantes mentalmente tras escribir cada método es el mejor seguro.

La simetría de la estructura se refleja en el código: los dos métodos son espejo el uno del otro.

Fíjate en el paso 2 de insertar_al_inicio, que no existía en la lista simple: el antiguo primer nodo debe devolver la mirada al nuevo (self.cabeza.anterior = nuevo). Es la asignación extra que mantiene el invariante de las flechas correspondidas. Olvidarla no rompe el recorrido hacia delante —el fallo queda agazapado— pero corta el recorrido hacia atrás justo en ese punto: el tipo de error silencioso más difícil de depurar.

Aquí está el titular de la lección, y hay que leerlo con su letra pequeña: teniendo una referencia al nodo, borrar (o insertar junto a él) es O(1) puro, sin caminar la lista ni buscar al anterior — el nodo ya lo trae consigo.

Detalles que marcan la diferencia:

• borrar_nodo construye dos puentes, uno por sentido, y cada uno tiene su caso frontera (primero/último). Cuatro ramas, todas necesarias.
• Las dos líneas de "higiene" (nodo.anterior = None, etc.) evitan que un nodo ya retirado siga reteniendo referencias a la lista viva — y de paso, que alguien lo use como punto de partida de un recorrido fantasma.
• Compara con la lista simple: allí, borrar exigía haber llegado con la pareja anterior/actual (O(n) de búsqueda previa salvo en la cabeza). Aquí, si guardaste la referencia al nodo (por ejemplo, el nodo del historial donde estás situado), el borrado es instantáneo. La ventaja solo se materializa si conservas referencias a nodos; si siempre empiezas buscando desde la cabeza, la lista doble no te ahorra la búsqueda O(n).

__reversed__ es el método mágico que Python invoca al escribir reversed(lista): empezamos por la cola y caminamos por las flechas anterior. En la lista simple este método era sencillamente imposible de escribir con coste razonable (habría que rebuscar el anterior de cada nodo, O(n²), o copiar la lista entera). El separador <-> de __str__ recuerda que ahora las flechas van en ambos sentidos.

¿Cuándo elegir cada una?

• Simple: cuando solo se avanza en un sentido y las modificaciones se concentran en los extremos o durante un recorrido hacia delante. Menos memoria, menos código, menos errores posibles.
• Doble: cuando se necesita navegar hacia atrás, o borrar/mover elementos a partir de referencias guardadas a sus nodos. El historial que viene ahora es el caso canónico.

Cada vez que un miembro del equipo abre una tarea, TaskFlow la anota en su historial. El usuario quiere moverse por ese historial como por las páginas de un navegador: atrás y adelante. Con la lista doble, el historial es la estructura y la posición actual es simplemente una referencia a un nodo:

Puntos a saborear:

• atras() y adelante() son O(1) puros: mover una referencia por una flecha. Con una lista simple, atras() habría exigido recorrer desde la cabeza hasta el nodo previo — O(n) por pulsación de botón.
• self.actual es la materialización de "la ventaja solo vale si conservas referencias a nodos": el historial vive precisamente de guardar una.
• Las comprobaciones is not None en cadena evitan tanto el historial vacío como salirse por los extremos: en la primera y la última tarea, los botones simplemente no se mueven.

En 02-05 completarás este historial con un matiz clásico de los navegadores: qué pasa con las tareas "adelante" cuando visitas una nueva desde mitad del historial.

En el módulo 1 quedó sembrada la mención a collections.deque, y ahora ya puedes entender su carné de identidad: deque está implementada en C como una estructura doblemente enlazada por bloques — no un nodo por elemento, sino nodos que son bloques de 64 huecos enlazados entre sí en ambos sentidos. Esa hibridación le da inserciones y borrados O(1) por ambos extremos con mucho menos sobrecoste de memoria por elemento que nuestra lista doble artesanal. Es la respuesta profesional de Python al patrón "entrar y salir por los dos extremos", y será protagonista en el módulo 4 cuando construyamos colas y deques; aquí nos basta con saber que existe y que, por dentro, es pariente directa de lo que acabas de programar.

• Actualizar una flecha y olvidar la de vuelta. El error estrella: tras a.siguiente = b, casi siempre falta b.anterior = a. El síntoma es traicionero porque el recorrido hacia delante funciona y el fallo solo aflora al ir hacia atrás. Verifica cada método contra el invariante n.siguiente.anterior is n.
• Los cuatro casos frontera de borrar_nodo. Primero, último, único elemento y nodo interior tocan ramas distintas. Borrar el único nodo debe dejar cabeza y cola a None a la vez; prueba siempre ese caso.
• Usar un nodo ya borrado. Si guardaste una referencia a un nodo y luego alguien lo borró, tus flechas apuntan al vacío (o a None, gracias a la higiene del método). En diseños con referencias vivas, define quién es responsable de invalidarlas — como hace HistorialTareas moviendo self.actual solo a través de sus métodos.
• Pagar la lista doble sin usarla. Si tu código nunca recorre hacia atrás ni guarda referencias a nodos, estás pagando una flecha extra por nodo y el doble de recableados a cambio de nada: vuelve a la lista simple. Elegir la estructura mínima suficiente también es optimizar.
• Consejo: al depurar, imprime la lista en ambos sentidos (list(lista) y list(reversed(lista))) y compara: deben ser exactamente inversas. Si no lo son, hay una flecha anterior traicionada, y el punto donde divergen te dice cuál.

Ejercicio 1 — buscar_nodo y borrado por id. Añade a ListaDoblementeEnlazada un método buscar_nodo(condicion) que devuelva el nodo (no el dato) que cumpla la condición, o None. Úsalo junto a borrar_nodo para eliminar del historial la tarea con id 2. ¿Cuál es el coste total de la operación combinada y en qué parte se concentra?

Ejercicio 2 — insertar_antes. Escribe el método insertar_antes(nodo, dato), simétrico de insertar_despues, con coste O(1). Cuidado con el caso en que nodo sea la cabeza. Comprueba con un ejemplo que los invariantes se mantienen imprimiendo la lista en ambos sentidos.

Ejercicio 3 — Detectar la flecha traicionada. Escribe una función verificar(lista) que devuelva True si la lista cumple los invariantes de la lección (cabeza sin anterior, cola sin siguiente, y flechas correspondidas en todos los nodos) y False en caso contrario. Después rompe adrede una flecha anterior de una lista de prueba y comprueba que verificar la detecta.

Solución 1:

El coste total es O(n), pero todo el coste está en la búsqueda; el borrado en sí es O(1). Esta separación es la moraleja de la lección: la lista doble abarata el modificar, no el encontrar. Para abaratar el encontrar hará falta el índice por id del módulo 5 — que, combinado con esta lista (un dict de id → nodo), dará borrados totales en O(1). Nota el detalle de recolocar historial.actual si estaba sobre el nodo borrado: es el error "usar un nodo ya borrado" atajado de raíz.

Solución 2:

El orden de las cuatro asignaciones sigue la regla de siempre ampliada: primero el nuevo mira a ambos lados, después los vecinos le devuelven la mirada. Y dentro de la segunda parte, nodo.anterior.siguiente = nuevo debe ir antes de nodo.anterior = nuevo, porque la primera línea todavía necesita el valor antiguo de nodo.anterior.

Solución 3:

Comprobamos las flechas con is (identidad de nodos, no igualdad de datos) y rematamos verificando que el recorrido muere en lista.cola — así cazamos también colas fantasma. Una función como esta, llamada tras cada operación en los tests, convierte los errores silenciosos de flechas en fallos ruidosos e inmediatos: exactamente lo que quieres mientras desarrollas.

Con una segunda flecha por nodo, la lista doblemente enlazada elimina las dos limitaciones de la simple: ya se puede recorrer hacia atrás (__reversed__ desde la cola) y, teniendo el nodo, borrar o insertar a su lado es O(1) sin buscar a nadie — a cambio de más memoria por nodo y hasta cuatro flechas que mantener coherentes en cada operación, con sus invariantes y sus casos frontera. El historial navegable de TaskFlow demostró dónde brilla: atras() y adelante() como simples movimientos de una referencia. Y collections.deque quedó presentada como la versión profesional e híbrida de esta idea, esperándonos en el módulo 4. Ahora bien, todas nuestras listas —simples o dobles— comparten un rasgo: tienen un final, ese None que detiene los recorridos. En la próxima lección lo eliminaremos deliberadamente: haremos que el último nodo apunte al primero y obtendremos las listas circulares, perfectas para los turnos rotatorios — en TaskFlow, el reparto cíclico de tareas entre los miembros del equipo — siempre que aprendamos a recorrerlas sin caer en el bucle infinito.