Approach Summary
HashMap + doubly-linked list. Map stores key → node; list keeps usage order (head = MRU, tail = LRU). O(1) get and put.
How to Recognize This Pattern
- "Design a cache with O(1) get/put and eviction"
- Ordered hash map or manual DLL + map
Complexity Analysis
Time Complexity
O(1)
Space Complexity
O(capacity)
Tags
Hash Table Linked List Design