maintain a map of frequency → doubly linked list. each node tracks its frequency count. on get/put, move the node to the next frequency list. when evicting, remove from the lowest frequency list's tail.
the doubly linked list gives O(1) insertion and removal. hash maps provide O(1) access to nodes and frequency lists. this combines the benefits of both data structures.
data structures
- mapOfNodes: key → node for O(1) access
- mapOfLists: frequency → doubly linked list
- each list maintains LRU order within same frequency
- evict from lowest frequency, least recently used
complexity
O(1) for both get and put operations. space is O(capacity) for nodes and frequency lists. efficient cache implementation.