función obtener(c, url): nodo ← c.índice[url] # hash: O(1) esperado si nodo = nada: devolver nada mover_al_frente(c.lista, nodo) # lista doble: O(1) devolver nodo.imagenfunción guardar(c, url, imagen): si url está en c.índice: actualizar el nodo y moverlo al frente si no: si tamaño(c) = c.límite: viejo ← quitar_último(c.lista) # O(1) borrar c.índice[viejo.url] nodo ← agregar_al_frente(c.lista, url, imagen) c.índice[url] ← nodo
Con una caché de límite 3, así cambian las dos estructuras:
Paso 1 de 3. Caché con límite 3. La lista va de la más reciente (frente) a la menos reciente (final): a, b, c. Cada entrada del índice apunta al nodo de su url.Paso 2 de 3. obtener(c): el índice encuentra el nodo c (borde grueso) y mover_al_frente lo coloca el primero (relleno y asterisco). Las demás entradas siguen apuntando a sus nodos.Paso 3 de 3. guardar(d) con la caché llena: sale b, el último, de la lista y del índice (punteado). d entra al frente y al índice (relleno y asterisco).
Borde grueso: lo que se compara. Relleno con asterisco: lo que acaba de cambiar.
El invariante combinado: cada url del índice apunta a un nodo de la lista, y cada nodo de la lista está en el índice. Cada operación que toca una estructura toca también la otra.
Lee el recorrido de esta página. Al pasar al siguiente momento, este cuenta como leído.