LRU Cache Design

The insight: use a hash map that stores pointers to list nodes.

class LRUCache:
    capacity: integer
    map: HashMap<key, DListNode>
    head: DListNode  # dummy
    tail: DListNode  # dummy

For get(key):

$1.$ Look up node in hash map. $O(1)$

$2.$ Move node to front of list (most recently used). $O(1)$

$3.$ Return node's value

For put(key, value):

$1.$ If key exists, update value and move to front

$2.$ If new key and at capacity, remove node at back (LRU), delete from map

$3.$ Create new node, add to front, add to map

Every operation is $O(1)$.