Remember
- Most recent at the head, least recent at the tail. The tail is what gets evicted.
- A hit or an update moves the node to the head. A new key is inserted at the head.
- The hash map finds the node in O(1) and the doubly linked list unlinks it in O(1): together, O(1) everything.