LRU Cache en Python desde cero

Implementación del LRU Cache (Least Recently Used) en Python con O(1) en get y put. Dos versiones: lista doblemente enlazada con dict para entender el mecanismo, y versión compacta con collections.OrderedDict. Pregunta clásica de entrevistas técnicas.

				# LRU Cache en Python: implementación desde cero
# Dos enfoques: lista doblemente enlazada + dict, y OrderedDict

from typing import Optional
from collections import OrderedDict


# ?????????????????????????????????????????????????????????????
# Implementación 1: Lista doblemente enlazada + diccionario
# Todas las operaciones en O(1) amortizado
# ?????????????????????????????????????????????????????????????

class Node:
    """Nodo de la lista doblemente enlazada."""
    def __init__(self, key: int, value: int):
        self.key = key
        self.value = value
        self.prev: Optional['Node'] = None
        self.next: Optional['Node'] = None


class LRUCache:
    """
    LRU Cache con O(1) para get() y put().

    Estructura interna:
    - dict: key ? Node  (acceso O(1) al nodo)
    - Lista doblemente enlazada: head ? nodo más reciente ... nodo más antiguo ? tail

    Los nodos 'head' y 'tail' son centinelas vacíos para evitar
    comprobar None en cada operación.
    """

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache: dict = {}          # key ? Node

        # Centinelas: head.next = más reciente, tail.prev = más antiguo
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node: Node) -> None:
        """Desconecta un nodo de la lista."""
        prev = node.prev
        nxt = node.next
        prev.next = nxt
        nxt.prev = prev

    def _insert_front(self, node: Node) -> None:
        """Inserta un nodo justo después del centinela head (posición 'más reciente')."""
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        """
        Devuelve el valor asociado a key.
        Al acceder, el nodo se mueve al frente (más reciente).
        Devuelve -1 si no existe.
        """
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._insert_front(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        """
        Inserta o actualiza key?value.
        Si la clave ya existe, actualiza y mueve al frente.
        Si la cache está llena, elimina el elemento menos usado (tail.prev).
        """
        if key in self.cache:
            # Actualizar y promover
            node = self.cache[key]
            self._remove(node)
            node.value = value
            self._insert_front(node)
        else:
            if len(self.cache) >= self.capacity:
                # Eliminar el LRU: el nodo más cercano a tail
                lru = self.tail.prev
                self._remove(lru)
                del self.cache[lru.key]
            # Insertar nuevo nodo al frente
            node = Node(key, value)
            self._insert_front(node)
            self.cache[key] = node


# ?????????????????????????????????????????????????????????????
# Implementación 2: OrderedDict (versión compacta)
# OrderedDict mantiene el orden de inserción y permite move_to_end()
# ?????????????????????????????????????????????????????????????

class LRUCacheOD:
    """
    LRU Cache usando collections.OrderedDict.
    Más conciso; internamente también O(1) para get/put.
    """

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache: OrderedDict = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        # Mover al final = 'más reciente'
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            # Eliminar el primero = 'menos reciente'
            self.cache.popitem(last=False)


# ?????????????????????????????????????????????????????????????
# Tests
# ?????????????????????????????????????????????????????????????

def run_tests(CacheClass, name: str):
    print(f"n=== {name} ===")
    ok = 0
    total = 0

    def check(got, expected, msg):
        nonlocal ok, total
        total += 1
        status = "OK" if got == expected else f"FALLO (esperado {expected}, obtenido {got})"
        print(f"  {msg}: {status}")
        if got == expected:
            ok += 1

    # Test 1: operación básica
    c = CacheClass(2)
    c.put(1, 1)
    c.put(2, 2)
    check(c.get(1), 1, "get(1) tras put(1,1) put(2,2)")

    # Test 2: eviction del LRU
    c.put(3, 3)  # 2 era el LRU al hacer get(1), así que 2 se elimina
    check(c.get(2), -1, "get(2) tras insertar 3 — debe estar eviccionado")
    check(c.get(3), 3, "get(3) existe")

    # Test 3: actualización de valor existente
    c2 = CacheClass(2)
    c2.put(1, 10)
    c2.put(2, 20)
    c2.put(1, 100)  # actualiza clave 1, la convierte en más reciente
    c2.put(3, 30)   # clave 2 es el LRU ? se elimina
    check(c2.get(2), -1, "clave 2 eviccionada tras actualizar clave 1")
    check(c2.get(1), 100, "clave 1 actualizada a 100")

    # Test 4: capacidad 1
    c3 = CacheClass(1)
    c3.put(1, 1)
    c3.put(2, 2)
    check(c3.get(1), -1, "capacidad 1: clave 1 eviccionada")
    check(c3.get(2), 2, "capacidad 1: clave 2 existe")

    print(f"  ? {ok}/{total} tests pasados")


if __name__ == '__main__':
    run_tests(LRUCache, "LRUCache (lista doblemente enlazada)")
    run_tests(LRUCacheOD, "LRUCacheOD (OrderedDict)")