LRU Cache — Doubly Linked List + HashMap Implementation

# Python — manual DLL
class DLL:
    def __init__(self, key=0, val=0):
        self.key = key; self.val = val
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = {}  # key -> DLL node
        self.head = DLL()  # least recently used
        self.tail = DLL()  # most recently used
        self.head.next = self.tail
        self.tail.prev = self.head

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

    def _add_to_tail(self, node):
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev.next = node
        self.tail.prev = node

    def get(self, key):
        if key not in self.cache: return -1
        node = self.cache[key]
        self._remove(node)
        self._add_to_tail(node)
        return node.val

    def put(self, key, value):
        if key in self.cache:
            self._remove(self.cache[key])
        node = DLL(key, value)
        self._add_to_tail(node)
        self.cache[key] = node
        if len(self.cache) > self.cap:
            lru = self.head.next
            self._remove(lru)
            del self.cache[lru.key]

// Java
class LRUCache {
    class Node { int key, val; Node prev, next; Node(int k, int v){key=k;val=v;} }
    int cap; Map<Integer,Node> cache = new HashMap<>();
    Node head = new Node(0,0), tail = new Node(0,0);
    public LRUCache(int capacity) { cap=capacity; head.next=tail; tail.prev=head; }
    void remove(Node n) { n.prev.next=n.next; n.next.prev=n.prev; }
    void addTail(Node n) { n.prev=tail.prev; n.next=tail; tail.prev.next=n; tail.prev=n; }
    public int get(int key) {
        if (!cache.containsKey(key)) return -1;
        Node n = cache.get(key); remove(n); addTail(n); return n.val;
    }
    public void put(int key, int val) {
        if (cache.containsKey(key)) remove(cache.get(key));
        Node n = new Node(key, val); addTail(n); cache.put(key, n);
        if (cache.size() > cap) { Node lru=head.next; remove(lru); cache.remove(lru.key); }
    }
}