LRU 캐시 구현

class Node:
    def __init__(self, key=0, val=0):
        self.key, self.val = key, val
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.map = {}                           # key -> Node
        self.head, self.tail = Node(), Node()   # 더미 노드로 경계 처리를 없앤다
        self.head.next, self.tail.prev = self.tail, self.head

    def _remove(self, node):
        node.prev.next, node.next.prev = node.next, node.prev

    def _add_front(self, node):
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        if key not in self.map:
            return None
        node = self.map[key]
        self._remove(node)
        self._add_front(node)                  # 사용했으니 맨 앞으로
        return node.val

    def put(self, key, val):
        if key in self.map:
            node = self.map[key]
            node.val = val
            self._remove(node)
            self._add_front(node)
            return
        if len(self.map) == self.cap:
            lru = self.tail.prev                # 맨 뒤 = 가장 오래 쓰지 않은 노드
            self._remove(lru)
            del self.map[lru.key]
        node = Node(key, val)
        self.map[key] = node
        self._add_front(node)

    def keys(self):                       # 최근 → 오래된 순서
        out, n = [], self.head.next
        while n is not self.tail:
            out.append(n.key); n = n.next
        return out

c = LRUCache(3)
c.put(1, 'A'); c.put(2, 'B'); c.put(3, 'C')
print(c.keys())                         # [3, 2, 1]
print(c.get(1), c.keys())               # A [1, 3, 2]
print(c.get(9))                          # None
c.put(4, 'D')
print(c.keys(), 2 in c.map)              # [4, 1, 3] False
c.put(3, 'E')
print(c.keys(), c.get(3))               # [3, 4, 1] E

from collections import OrderedDict

class LRU2:
    def __init__(self, cap):
        self.cap, self.d = cap, OrderedDict()

    def get(self, k):
        if k not in self.d: return None
        self.d.move_to_end(k)               # 사용한 키를 맨 뒤(최근)로
        return self.d[k]

    def put(self, k, v):
        self.d[k] = v
        self.d.move_to_end(k)
        if len(self.d) > self.cap:
            self.d.popitem(last=False)      # 맨 앞(가장 오래된) 항목 제거

c2 = LRU2(3)
for k, v in [(1, 'A'), (2, 'B'), (3, 'C')]: c2.put(k, v)
c2.get(1)
c2.put(4, 'D')
print(list(c2.d))                      # [3, 1, 4] (오래된 → 최근)

from functools import lru_cache

@lru_cache(maxsize=2)
def sq(n): return n * n

sq(1); sq(2); sq(1); sq(3)
print(sq.cache_info())              # CacheInfo(hits=1, misses=3, maxsize=2, currsize=2)

import java.util.LinkedHashMap;
import java.util.Map;

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    LRUCache(int capacity) {
        super(16, 0.75f, true);          // true: 접근 순서(access-order)로 유지
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;           // 넘치면 가장 오래된 항목을 제거
    }
}

LRUCache<Integer, String> cache = new LRUCache<>(3);
cache.put(1, "A"); cache.put(2, "B"); cache.put(3, "C");
cache.get(1);
cache.put(4, "D");
System.out.println(cache.keySet());          // [3, 1, 4]
System.out.println(cache.containsKey(2));    // false