CSE Roadmap

Core tier · about 4 hours · 6 parts

Part 3 of 6 · 2 min read

The two structures

A map to find, a list to order.

Two simple tries fail the cost target.

  • A map alone. Finding a key is quick, but a map has no order of use. To find the least recently used key, every entry would have to be scanned, which is linear time.
  • A list alone. Order of use is easy to keep, with the newest at the front and the oldest at the back. But finding a key means walking the list, which is linear time again.

The answer is to use both together. A hash map from key to node gives constant-time lookup. A doubly linked list of nodes keeps the order of use, newest at the front and oldest at the back. Each node knows its neighbours on both sides, so a node that is already in hand can be unlinked and moved to the front in constant time. The map is the index, and the list is the order.

 map:   key -> node
 list:  head <-> [newest] <-> ... <-> [oldest] <-> tail     (head and tail are sentinels)

Two sentinel nodes, head and tail, hold no data. They make every real node have a neighbour on both sides, so unlinking and inserting never needs a special case for the ends.

Class Job in one sentence
LruCache<K,V> Holds the map, the list, the capacity and counters, and exposes get and put
Node (inner class) Holds a key, a value and two links

Why does the node store the key as well as the value? When the oldest node is removed from the list, the map entry must be removed too, and the map is keyed by the key. The node is the only place that remembers it.

Check yourself: 1. Why does a map alone not meet the cost target? 2. Why does the list need links in both directions? 3. Why does a node hold its key?