Linked Lists
A hash map over a doubly linked list
Two structures, each covering the other's weakness. The most useful design pattern in the unit.
Key idea
The requirement that forces the design
A cache with a size limit needs three things in constant time: find an entry by key, mark an entry as most recently used, and evict the least recently used one.
A dict does the first and knows nothing about ordering. A list knows about ordering but finding an entry means scanning. Neither alone is enough, and the answer is to use both, pointing at each other.
Why it works
What each structure is responsible for
The doubly linked list holds the entries in usage order, most recent at one end and least recent at the other. It can move a node or drop the end node in constant time, given a reference to that node.
The dict maps each key to the node itself. That is the whole trick: the dict supplies the reference that makes the list operations constant time.
Without the dict you would have to find the node by walking. Without the list you would have no ordering. Together every required operation is O(1).
Key idea
Why doubly linked
Removing a node from the middle requires rewiring the node before it, and in a singly linked list you cannot get there from the node itself. So each node stores both prev and next.
That is the only reason. If nothing ever had to be removed from the middle, a singly linked list would do.
Tip
Two sentinels remove every boundary case
head and tail are permanent nodes that hold no data and are never removed. Because of them, every real node always has both a prev and a next, so unlink and insert_after need no null checks at all.
This is the dummy head from earlier in the unit, doubled. Look at how short those two functions are; without sentinels each would need branches for the empty list, the first node, and the last node.
Why it works
Keep the key in the node
Eviction removes the node at the least recent end, and it must also remove that entry from the dict. To do that you need the key, and you have a node.
So the node stores its own key as well as its value. Forgetting this produces a design where eviction cannot clean up the dict, which grows forever and quietly breaks the size limit. It is the most common flaw in a first attempt at this.
The two operations in terms of the pieces
A read: look the key up in the dict. If absent, report a miss. If present, unlink the node and reinsert it at the most recent end, then return its value.
A write: if the key exists, update the value and move the node to the most recent end. If not, create a node, insert it at the most recent end, and record it in the dict. Then, if the size now exceeds the limit, unlink the node at the least recent end and delete its key from the dict.
Both are three or four lines once unlink and insert_after exist. Build those first.
Cost of the combined structure
Time for a single get or put on the cache, and total space for a cache holding at most k entries.
Time
Space
Lru Cache
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.