SimuVedaAlgorithms Lab Open in the lab

Lists, stacks & queues / Intermediate

LRU Cache (Hash Map + Linked List) Visualizer

A hash map finds a key’s node in O(1). A doubly linked list keeps nodes in use order: most recent at the head, least recent at the tail. A hit moves the node to the head; a miss adds at the head and, if full, removes the tail.

Start the LRU Cache (Hash Map + Linked List) simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(1)
Average timeO(1)
Worst timeO(1)
Extra spaceO(capacity)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. An empty cache with room for 3. The head is the most recently used key, the tail the least.
  2. Access 1: not in the hash map. A miss.
  3. Add 1 at the head and record it in the hash map.
  4. Access 2: not in the hash map. A miss.
  5. Add 2 at the head and record it in the hash map.
  6. Access 3: not in the hash map. A miss.
  7. Add 3 at the head and record it in the hash map.
  8. Access 1: the hash map finds it at once. A hit.
  9. Move 1 to the head: it is now the most recently used.
  10. Access 4: not in the hash map. A miss.
  11. The cache is full. The tail, 2, is the least recently used: evict it.
  12. Add 4 at the head and record it in the hash map.
  13. Access 2: not in the hash map. A miss.
  14. The cache is full. The tail, 3, is the least recently used: evict it.
  15. Add 2 at the head and record it in the hash map.
  16. Access 5: not in the hash map. A miss.
  17. The cache is full. The tail, 1, is the least recently used: evict it.
  18. Add 5 at the head and record it in the hash map.
  19. Access 1: not in the hash map. A miss.
  20. The cache is full. The tail, 4, is the least recently used: evict it.
  21. … 1 more steps …
  22. Access 3: not in the hash map. A miss.
  23. The cache is full. The tail, 2, is the least recently used: evict it.
  24. Add 3 at the head and record it in the hash map.
  25. Done: 1 hit, 8 misses. Cache, most recent first: 3, 1, 5.

Try it with your own input →

LRU cache (hash map + linked list) in Java, Python, C++, C and JavaScript

int get(int key) {
  Node n = map.get(key);
  if (n == null) return -1;      // miss
  moveToHead(n);                  // now most recent
  return n.val;
}
void put(int key, int val) {
  if (map.size() == cap) {
    Node lru = tail.prev;         // least recent
    remove(lru); map.remove(lru.key);
  }
  Node n = new Node(key, val); addToHead(n); map.put(key, n);
}
from collections import OrderedDict

class LRUCache:
    def __init__(self, cap):
        self.cap, self.map = cap, OrderedDict()

    def get(self, key):
        if key not in self.map:
            return -1  # miss
        self.map.move_to_end(key)  # now most recent
        return self.map[key]

    def put(self, key, val):
        if len(self.map) == self.cap:
            self.map.popitem(last=False)  # least recent
        self.map[key] = val
        self.map.move_to_end(key)
// cap, map (key -> Node*), and a doubly linked list with head/tail sentinels
int get(int key) {
  auto it = map.find(key);
  if (it == map.end()) return -1;      // miss
  Node* n = it->second;
  moveToHead(n);                       // now most recent
  return n->val;
}
void put(int key, int val) {
  if ((int)map.size() == cap) {
    Node* lru = tail->prev;            // least recent
    remove(lru); map.erase(lru->key); delete lru;
  }
  Node* n = new Node(key, val); addToHead(n); map[key] = n;
}
/* cap, a hash map (key -> Node*) and a doubly linked list with head/tail sentinels;
   mapGet/mapPut/mapRemove, moveToHead, addToHead and removeNode are small helpers */
int get(LRU* c, int key) {
  Node* n = mapGet(c->map, key);
  if (n == NULL) return -1;            // miss
  moveToHead(c, n);                    // now most recent
  return n->val;
}
void put(LRU* c, int key, int val) {
  if (c->size == c->cap) {
    Node* lru = c->tail->prev;         // least recent
    removeNode(lru); mapRemove(c->map, lru->key); free(lru); c->size--;
  }
  Node* n = newNode(key, val); addToHead(c, n); mapPut(c->map, key, n); c->size++;
}
// A Map keeps keys in insertion order, so the first key is the least recent.
class LRUCache {
  constructor(cap) { this.cap = cap; this.map = new Map(); }
  get(key) {
    if (!this.map.has(key)) return -1;   // miss
    const val = this.map.get(key);
    this.map.delete(key); this.map.set(key, val);   // now most recent
    return val;
  }
  put(key, val) {
    if (this.map.size === this.cap) {
      const lru = this.map.keys().next().value;   // least recent
      this.map.delete(lru);
    }
    this.map.set(key, val);
  }
}

In an interview

LeetCode 146, LRU Cache: get and put in O(1), throwing out the least recently used key when full.

The list must be doubly linked so a node can unlink itself in O(1). Dummy head and tail nodes remove the empty-list special cases. Java’s LinkedHashMap with accessOrder = true does all of this for you.

More lists, stacks & queues