Semana 8 - Listas Doblemente Enlazadas

 Listas Doblemente Enlazadas

Esta semana evolucionamos nuestra estructura de lista un paso más allá. En una lista simplemente enlazada (Semanas 4-7), la navegación es unidireccional: solo podemos avanzar (.sig). En una lista doblemente enlazada, cada nodo se vuelve más complejo y contiene dos punteros: sig (para el siguiente nodo) y ant (para el nodo anterior). Esto nos da el poder de recorrer la lista en ambas direcciones (hacia adelante y hacia atrás), resolviendo problemas donde necesitamos acceder al predecesor de un nodo.

El desafío de esta semana fue manejar la complejidad adicional de los punteros. El costo es obvio: más memoria por cada nodo (para el puntero ant) y operaciones de inserción y borrado más delicadas, ya que hay más "cables" que conectar y desconectar. La estructura del nodo ahora es: (Nodo ant, int info, Nodo sig). El puntero raiz sigue apuntando al inicio. El primer nodo tiene ant = null y el último nodo tiene sig = null.

La operación de insertar(pos, x) en medio de la lista es el ejemplo perfecto de esta complejidad. Si queremos insertar nuevo entre reco y siguiente (donde reco es el nodo en pos-2 y siguiente = reco.sig):

• En una lista simple, solo actualizábamos 2 punteros (reco.sig = nuevo y nuevo.sig = siguiente).

• En una lista doble, debemos actualizar 4 punteros para mantener la integridad de la cadena en ambas direcciones:

  1. reco.sig = nuevo (El anterior apunta hacia adelante al nuevo).

  2. nuevo.ant = reco (El nuevo apunta hacia atrás al anterior).

  3. nuevo.sig = siguiente (El nuevo apunta hacia adelante al siguiente).

  4. siguiente.ant = nuevo (El siguiente apunta hacia atrás al nuevo).

De manera similar, la operación borrar(pos) en medio (borrar prox) requiere "puentear" en ambas direcciones. Se debe encontrar el nodo anterior (reco) y el nodo siguiente (siguiente = prox.sig):

1. reco.sig = siguiente (El anterior "salta" al siguiente).

2. if (siguiente != null) siguiente.ant = reco (El siguiente "salta" hacia atrás al anterior).

Conclusión 

La lista doblemente enlazada es otro ejemplo perfecto de un balance (trade-off). El costo es claro: cada nodo ocupa más memoria (porque tiene dos punteros, ant y sig) y la lógica para insertar y borrar es más compleja (hay que reconectar 4 enlaces en lugar de 2), lo que aumenta el riesgo de errores. El beneficio es una flexibilidad inmensa. Como estudiante, veo su valor en aplicaciones que uso todos los días: el botón "Atrás" de un navegador web (que necesita ir al nodo anterior), el botón "Canción Anterior" en un reproductor de música, o un editor de texto donde puedes mover el cursor en ambas direcciones. Me enseña que a veces vale la pena pagar un costo en memoria y complejidad para ganar una funcionalidad que es crucial para el usuario.