GUÍA 19-10-26 Estructuras de Datos

CN122 · lunes 19/10/2026 · 13:00-14:15 · Sesión 20

Listas doblemente ligadas

EL NODO CON DOS ENLACES

• typedef struct Nodo { int dato; struct Nodo *ant, *sig; } Nodo;

Cada nodo conoce a su predecesor y a su sucesor. Se paga un apuntador más por nodo y se gana recorrido bidireccional y eliminación sin buscar el anterior.

LA VENTAJA DECISIVA

Para eliminar un nodo del que ya tienes la dirección, la lista simple exige recorrer desde el inicio para hallar el anterior: O(n). La doble lo hace en O(1) porque el anterior está ahí.

• p->ant->sig = p->sig; if (p->sig) p->sig->ant = p->ant; free(p);

INSERCIÓN

Hay cuatro enlaces que actualizar y el orden importa. Conviene escribirlos siempre en la misma secuencia: primero los del nodo nuevo, después los de los vecinos.

1. nuevo->ant = p;

2. nuevo->sig = p->sig;

3. if (p->sig) p->sig->ant = nuevo;

4. p->sig = nuevo;

CENTINELAS

Con un nodo cabeza y un nodo cola ficticios, ningún apuntador es NULL y desaparecen todos los casos especiales. El código se vuelve notablemente más corto y más difícil de romper. Es la forma en que se implementan las listas de las bibliotecas estándar.

DOBLEMENTE LIGADA Y CIRCULAR

Combinando ambas ideas, el último apunta al primero y el primero al último. Es la estructura de std::list en C++ y de la lista de tareas del kernel de Linux.

APLICACIONES

• Navegación con atrás y adelante.
• Deshacer y rehacer.
• Caché LRU, combinada con una tabla hash.

PRÁCTICA

Implementar la lista doble con centinelas y una caché LRU sencilla.