LRU cache

The map finds a key in O(1) but has no order; the list keeps order in O(1) but cannot find anything. Store the list node as the map's value and every operation - including eviction - becomes constant time.