Implement an LRU (Least Recently Used) Cache with O(1) get and put. Use: HashMap + Doubly Linked List. Methods: get(key) → value or -1, put(key, value) → evict LRU if capacity exceeded. Explain: why DLL (O(1) remove from middle), why HashMap (O(1) lookup), dummy head/tail nodes pattern. Walk through an example with capacity=3.
