Leetcode #146 | #Medium | [[Связный список]] | [[Хэш-таблицы]] | [[Design]]
## Идея
HashMap {ключ: Node} и двусвязный список из Node (next, prev, key, val)  
Для удобства фиктивный head и tail. Обращение - удаляем из места и ставим в конец. Если капасити превышено удаляем head.next
## [[Big-O]]
- Время ```O(1)```
- Память  ```O(N)```
## Код
```Java
class LRUCache {
    class Node {
        int key, val;
        Node prev, next;
        Node(int k, int v) { key = k; val = v; }
    }
    private int cap;
    private Map<Integer, Node> map = new HashMap<>();
    private Node head = new Node(0, 0), tail = new Node(0, 0);

    public LRUCache(int capacity) {
        cap = capacity;
        head.next = tail; tail.prev = head;
    }
    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        remove(node); insert(node);
        return node.val;
    }
    public void put(int key, int value) {
        if (map.containsKey(key)) remove(map.get(key));
        Node node = new Node(key, value);
        insert(node); map.put(key, node);
        if (map.size() > cap) {
            Node lru = head.next;
            remove(lru); map.remove(lru.key);
        }
    }
    private void remove(Node node) { node.prev.next = node.next; node.next.prev = node.prev; }
    private void insert(Node node) {
        Node prev = tail.prev;
        prev.next = node; node.prev = prev;
        node.next = tail; tail.prev = node;
    }
}
```