Link: https://leetcode.com/problems/lru-cache/
Solution:
Topics: linked list, hash map
Intuition
This is not a difficult problem, but the implementation is extremely annoying. Basically, we need o(1)
removals and insertions. The only data structure that supports this are doubly linked lists. We use a hash map to keep pointers to nodes so we don’t have to traverse the whole list for get
calls.
The implementation is minefield of edge cases, but there is way to make it more manageable. Initialize the linked list with a dummy head and dummy tail (and connect them). This removes so many edge case because now we we can handle removal or insertion of any node the same way! More specifically, each node inserted is guaranteed not to be the head or the tail…we interact with the list by inserting new nodes (most recent) into head.next
and removing LRU nodes by grabbing tail.prev
.
Also, its highly useful to define methods add
and remove
.
Implementation
Mnemonic
You have a measuring calliper. As you put more marbles in a line between the callipers, the callipers must spread. If remove all marbles, the callipers arms are touching each other. The arms represent the dummy nodes.
Visual
Review 1
The two dummy nodes implementation is amazing…use it. Remember to implement add/remove methods.