Caso real

La lista de las cachés LRU

Una caché LRU («menos usado recientemente») guarda un número limitado de elementos y, cuando se llena, expulsa el que lleva más tiempo sin usarse. Muchas implementaciones usan una lista doble: cada vez que se usa un elemento, se mueve al principio; cuando hay que expulsar, se quita el último. La unidad 8 la construye completa, junto con una tabla hash que encuentra el nodo.

Aplica la misma condición a otro caso: mover algo al principio de una lista.

Un editor guarda las pestañas recientes en una lista doble: al abrir una pestaña que ya existe, se mueve al principio. ¿Qué hace falta para que mover al principio sea O(1)?Que la lista esté ordenada por nombre, para encontrar la pestaña con búsqueda binaria sobre los nodosQue la lista sea simple y no doble, porque así hay menos enlaces que cambiar al mover el nodoLlegar al nodo de la pestaña sin recorrer, por ejemplo con una tabla que guarde el nodo de cada unaNada: mover al principio es siempre O(1) en una lista, tenga o no el nodo de la pestaña a mano