GUÍA 21-10-26 Estructuras de Datos

CN122 · miércoles 21/10/2026 · 13:00-14:15 · Sesión 21

Taller de listas doblemente ligadas · Caché LRU

SESIÓN DE PRÁCTICA

Se aplica la lista doble a un problema real donde su ventaja es indispensable.

CACHÉ LRU

Una caché de capacidad fija que, al llenarse, desaloja el elemento usado hace más tiempo. Requiere dos operaciones en O(1): mover un elemento al frente al usarlo, y eliminar el del final al desalojar.

• Lista doble — mantiene el orden de uso; mover al frente es O(1) porque se conoce el anterior.
• Tabla hash — mapea la clave al nodo, para localizarlo en O(1) sin recorrer.

Ninguna de las dos estructuras basta sola. La combinación es el ejemplo más claro del curso de que las estructuras se componen, no se eligen de una lista.

OPERACIONES

1. get(clave): si está en la tabla, mover su nodo al frente y devolver el valor.

2. put(clave, valor): si existe, actualizar y mover al frente.

3. Si no existe y hay espacio, insertar al frente y registrar en la tabla.

4. Si no existe y está llena, eliminar el último, borrarlo de la tabla e insertar el nuevo al frente.

DEPURACIÓN

• Verificar la consistencia: recorrer hacia adelante y hacia atrás debe dar la misma secuencia invertida.
• Probar capacidad 1, que descubre casi todos los errores de casos frontera.

PRÁCTICA

Implementar la caché LRU completa y probarla con una secuencia de accesos conocida.