Why it works
- The list is kept in order of use: every get and put moves its node right after head, so the node right before tail is always the one used longest ago.
- The map gives a key's node in one step, and prev links let a node be taken out of the middle with two assignments. Nothing is searched, so get and put are O(1).
- head and tail are dummies: a node always has neighbours on both sides, so taking out the only node or adding to an empty list needs no special case.
Complexity
Time O(1) per get and put: one map lookup and a fixed number of links. Memory O(capacity): a node and a map entry per key.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗