Linked List & Design

LRU Cache

A cache of fixed size that throws out the key nobody has touched for longest - and does it in a constant number of steps.

Medium

Problem

Design a data structure that follows the Least Recently Used (LRU) policy. Implement LRUCache(capacity), get(key) which returns the value or -1, and put(key, value) which inserts or updates and evicts the least recently used key when over capacity.

get and put must each take a constant number of steps, no matter how big the cache is.
Reading a key with get counts as using it.
Updating an existing key counts as using it.

Examples

Input: capacity 2: put(1,1), put(2,2), get(1), put(3,3), get(2), put(4,4), get(1), get(3), get(4)

Output: 1, -1, -1, 3, 4

put(3,3) evicts key 2, which was used least recently; put(4,4) then evicts key 1.

Approach

Time O(1) get / putSpace O(capacity)

A map finds a key instantly but knows nothing about order. A doubly linked list - a chain where each node points both forwards and backwards - can move an item in one step but cannot find it. Use both together.
The map stores key -> the node holding it. The chain runs from most recently used at the front to least recently used at the back. Two empty placeholder nodes sit at each end so you never have to special-case the first or last item.
get: if the key is there, take its node out of the chain, put it back at the front, and return its value.
put: update and move to front if the key exists; otherwise add a new node at the front, and if the size exceeds capacity, remove the node before the tail and delete its key from the map.

Brute force: Keep an array in recency order. Finding a key and moving it means walking the array each time.

Common mistakes

Forgetting to move a key to the front on get, so reads do not count as use.
Removing the list node but not the map entry, or the other way round.
The node must store its key, or you cannot delete the evicted entry from the map.

Step through it

Pick an input and play the algorithm step by step. The highlighted line in the code follows each step, and you can edit the code to experiment.

LRU CACHE`get` counts as using a key, so it moves to the most-recently-used end.

Operations

1.put(1, 1)

2.put(2, 2)

3.get(1)

4.put(3, 3)

5.get(2)

6.put(4, 4)

7.get(1)

8.get(3)

9.get(4)

Solution · JS

1class Node {

2 constructor(key, value) {

3 this.key = key;

4 this.value = value;

5 this.prev = null;

6 this.next = null;

7 }

10class LRUCache {

11 constructor(capacity) {

12 this.capacity = capacity;

13 this.map = new Map(); // key -> node

14 // head.next is the most recent, tail.prev the least recent

15 this.head = new Node(-1, -1);

16 this.tail = new Node(-1, -1);

17 this.head.next = this.tail;

18 this.tail.prev = this.head;

19 }

21 remove(node) {

22 node.prev.next = node.next;

23 node.next.prev = node.prev;

24 }

26 addFront(node) {

27 node.prev = this.head;

28 node.next = this.head.next;

29 this.head.next.prev = node;

30 this.head.next = node;

31 }

33 moveToFront(node) {

34 this.remove(node);

35 this.addFront(node);

36 }

38 get(key) {

39 if (!this.map.has(key)) return -1;

40 const node = this.map.get(key);

41 this.moveToFront(node);

42 return node.value;

43 }

45 put(key, value) {

46 if (this.map.has(key)) {

47 const node = this.map.get(key);

48 node.value = value;

49 this.moveToFront(node);

50 return;

51 }

53 const node = new Node(key, value);

54 this.map.set(key, node);

55 this.addFront(node);

57 if (this.map.size > this.capacity) {

58 const lru = this.tail.prev;

59 this.remove(lru);

60 this.map.delete(lru.key);

61 }

62 }

63}

class Node {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map(); // key -> node
    // head.next is the most recent, tail.prev the least recent
    this.head = new Node(-1, -1);
    this.tail = new Node(-1, -1);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

addFront(node) {
    node.prev = this.head;
    node.next = this.head.next;
    this.head.next.prev = node;
    this.head.next = node;
  }

moveToFront(node) {
    this.remove(node);
    this.addFront(node);
  }

get(key) {
    if (!this.map.has(key)) return -1;
    const node = this.map.get(key);
    this.moveToFront(node);
    return node.value;
  }

put(key, value) {
    if (this.map.has(key)) {
      const node = this.map.get(key);
      node.value = value;
      this.moveToFront(node);
      return;
    }

const node = new Node(key, value);
    this.map.set(key, node);
    this.addFront(node);

if (this.map.size > this.capacity) {
      const lru = this.tail.prev;
      this.remove(lru);
      this.map.delete(lru.key);
    }
  }
}

Chain of nodes · most recently used → least recently used

Doubly linked list

HEAD

→←

TAIL

op —

size 0/2

return —

MAPempty

Cap

Size

Key

—

Return

—

0 / 0

Speed1×

Execution log

steps appear here…

Solution

The same approach in JavaScript, Python, and Java. Each is a complete program that prints the examples above - JavaScript runs here, so edit it and try your own input.

LanguageEdit and run it here

JavaScript solution

Output

Run code to see output...

Comments

Loading comments...

LRU Cache

Problem

Examples

Approach

Common mistakes

Step through it

Solution

Comments

AI

System Design

Backend

Frontend

Fundamentals