Design LRU Cache
An LRU cache is a utility: no turn-taking referee or spatial state, just a single data structure that must honour a contract — O(1) reads, O(1) writes, and automatic eviction of the least-recently-used entry when the cache exceeds its capacity. No single standard data structure achieves all three simultaneously; the design combines two structures to meet the full contract.
See It in Action
The demo shows put, get, and LRU eviction for a bounded cache. Press ▶ Run example for a guided walkthrough that fills the cache, touches a key, then evicts the least-recently-used one — or drive it yourself.
Clarifying Requirements
The functional requirements we commit to: get(key) returns the value associated with the key
if it exists, or -1 on a miss, and counts as a use of that key; put(key, value) stores the
key-value pair, updating the value in place if the key already exists, and counts as a use; when
a put causes the number of entries to exceed the capacity, the least-recently-used key is evicted
before the new entry is inserted; capacity is a positive integer fixed at construction time.
Out of scope for this walkthrough: TTL-based expiry, the LFU (least-frequently-used) variant,
runtime capacity resizing, persistence across restarts, and thread-safety. Thread-safety deserves
a brief mention — any shared cache needs its get and put guarded together as a critical
section — but the full treatment belongs in the key-value store case study. The decision to exclude
it here lets us focus entirely on the O(1) data structure design.
The decision logic for both operations is captured below.
Core Entities
The contract is the hard constraint: get and put must both run in O(1), and put on a full
cache must evict the least-recently-used entry — also in O(1). That rules out a single data
structure. Before reading on, decide what combination of structures supports lookup by key,
promotion to most-recently-used, and eviction of the least-recently-used, all in constant time.
Decision checkpoint
Lookup by key, promote to most-recently-used, and evict the least-recently-used must each be O(1). What data structure(s) give you all three?
Reading the requirements for nouns that carry state confirms a short list. A Node is one cache
entry — it holds a key, a value, and the pointers that link it to its neighbours in a recency-ordered
sequence. An LRUCache is the cache itself — it owns the hash map that enables O(1) lookup by key
and the doubly-linked list that enables O(1) promotion to the front and O(1) eviction from the back.
A doubly-linked list keeps a prev and next pointer on every node, so any node can be unlinked in
O(1) given just a pointer to it — a singly-linked list can't, because from a node it can't reach its
predecessor to repair the link.
One consequence of the eviction rule is that the Node must store its key as well as its value. When the least-recently-used node is evicted from the tail of the list, the cache must also remove it from the hash map. Without the key on the node, that removal would require a reverse lookup — O(n) — which breaks the O(1) contract.
Two sentinel nodes — a dummy head and a dummy tail — permanently anchor the two ends of the list.
Real entries sit between them. Sentinels eliminate the null checks that make linked-list code
fragile: _remove and _push_front never need to handle "what if this is the first node" as a
special case.
The diagram below shows how the hash map and the doubly-linked list fit together. The map gives O(1) lookup; the list maintains recency order with O(1) promotion and eviction.
Designing the Classes
With the entities in hand, the next step is to derive each class's state and behavior directly from the requirements — adding a field only when a specific requirement demands it, and keeping each method signature at the design level before writing any implementation. The guiding principle is Tell, Don't Ask: callers tell the cache to get or put; they never inspect the internal list structure or make decisions about recency themselves.
Node
A cache entry obviously holds a value, and the linked list needs prev and next pointers. The
less obvious field is the key: should the node store its own key, or is the value enough? Before
reading on, trace what happens at eviction time and decide.
Decision checkpoint
When the cache evicts the least-recently-used node from the list tail, it must also delete that entry from the hash map. Does the Node need to store its key, or just its value?
The requirements say a cache entry holds an integer key and an integer value. That alone would make
Node a simple key-value pair. But the requirement that eviction must also remove the entry from the
hash map adds a third demand: the node must carry its key so the cache can call del cache[node.key]
without a reverse lookup. The requirement for O(1) eviction from the doubly-linked list adds the
fourth and fifth fields: a prev pointer and a next pointer.
Node exposes no behavior of its own. It is a pure data carrier — all decisions happen in LRUCache.
The complete state is key: int, value: int, prev: Node | None, next: Node | None.
LRUCache
Working through the requirements one by one: "capacity is fixed at construction time" demands a
_capacity: int field. "O(1) lookup by key" demands a _cache: dict[int, Node] hash map.
"O(1) promotion to the most-recently-used position" and "O(1) eviction from the
least-recently-used position" demand a doubly-linked list; the list needs two permanent anchors,
so _head: Node and _tail: Node are sentinel nodes initialized at construction and never moved.
The public behavior follows directly from the two operations the requirements name: get(key) -> int
and put(key, value) -> None. Both operations mutate recency, which means both need access to the
list. Rather than repeating four pointer assignments in every method, two private helpers own all
pointer arithmetic: _remove(node) unlinks a node from its current position, and _push_front(node)
inserts a node immediately after the dummy head. Every public method is then at most four lines.
The list runs most-recently-used just after the dummy head to least-recently-used just before the
dummy tail. The public surface is deliberately small: get and put. Keeping it small makes the
cache safe to extend — adding TTL or statistics later — without breaking callers.
Try It Yourself
Before reading the implementation, attempt it. Implement lru_cache(capacity, instructions) that
replays a sequence of commands and returns one output line per get.
Each instruction is a list of strings. Two commands exist:
["put", key, value]— store the integer key-value pair; update in place if the key exists; evict the least-recently-used entry first if the cache is now over capacity. Produces no output.["get", key]— return the value as a string, or"-1"on a miss. Bothgetandputcount as a use and refresh recency.
Keys and values are integers passed as strings in the instruction list; parse them with int().
The entry function is named lru_cache and returns list[str].
Code Walkthrough
The reference design is two classes and two private helpers. Node is a plain data carrier with
four fields. LRUCache wires the hash map and the doubly-linked list together, keeping all pointer
arithmetic inside _remove and _push_front so the public methods stay readable.
Node's constructor takes the key and value the cache entry represents, then sets both pointer
fields to None. The None sentinels are immediately overwritten when the node is inserted into
the list, but initializing them avoids any "attribute not set" errors if the object is ever
inspected before insertion.
key lives on Node rather than only on LRUCache's dict. When the tail sentinel's predecessor
is evicted, the cache does del self._cache[lru.key] — without key on the node, that
deletion would require scanning the entire dict in reverse, costing O(n).
1class Node:
2 def __init__(self, key: int, value: int) -> None:
3 self.key: int = key
4 self.value: int = value
5 self.prev: "Node | None" = None
6 self.next: "Node | None" = None
Full Solution
1class Node:
2 def __init__(self, key: int, value: int) -> None:
3 self.key: int = key
4 self.value: int = value
5 self.prev: "Node | None" = None
6 self.next: "Node | None" = None
7
8
9class LRUCache:
10 def __init__(self, capacity: int) -> None:
11 self._capacity: int = capacity
12 self._cache: dict[int, Node] = {}
13 # Sentinel nodes eliminate null checks at list boundaries.
14 self._head: Node = Node(-1, -1)
15 self._tail: Node = Node(-1, -1)
16 self._head.next = self._tail
17 self._tail.prev = self._head
18
19 def _remove(self, node: Node) -> None:
20 prev = node.prev
21 nxt = node.next
22 if prev is not None:
23 prev.next = nxt
24 if nxt is not None:
25 nxt.prev = prev
26
27 def _push_front(self, node: Node) -> None:
28 node.prev = self._head
29 node.next = self._head.next
30 if self._head.next is not None:
31 self._head.next.prev = node
32 self._head.next = node
33
34 def get(self, key: int) -> int:
35 node = self._cache.get(key)
36 if node is None:
37 return -1
38 self._remove(node)
39 self._push_front(node)
40 return node.value
41
42 def put(self, key: int, value: int) -> None:
43 if key in self._cache:
44 node = self._cache[key]
45 node.value = value
46 self._remove(node)
47 self._push_front(node)
48 else:
49 node = Node(key, value)
50 self._cache[key] = node
51 self._push_front(node)
52 if len(self._cache) > self._capacity:
53 lru = self._tail.prev
54 if lru is not None and lru is not self._head:
55 self._remove(lru)
56 del self._cache[lru.key]
57
58
59def lru_cache(capacity: int, instructions: list[list[str]]) -> list[str]:
60 cache = LRUCache(capacity)
61 output: list[str] = []
62 for instruction in instructions:
63 command, *args = instruction
64 if command == "put":
65 cache.put(int(args[0]), int(args[1]))
66 elif command == "get":
67 output.append(str(cache.get(int(args[0]))))
68 return output
69
70if __name__ == "__main__":
71 capacity = int(input())
72 instructions = [input().split() for _ in range(int(input()))]
73 res = lru_cache(capacity, instructions)
74 for line in res:
75 print(line)
761import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.HashMap;
4import java.util.List;
5import java.util.Map;
6import java.util.Scanner;
7
8class Solution {
9 static class Node {
10 int key, value;
11 Node prev, next;
12 Node(int k, int v) { key = k; value = v; }
13 }
14
15 static class LRUCacheImpl {
16 int capacity;
17 Map<Integer, Node> cache = new HashMap<>();
18 Node head = new Node(-1, -1);
19 Node tail = new Node(-1, -1);
20
21 LRUCacheImpl(int cap) {
22 capacity = cap;
23 head.next = tail;
24 tail.prev = head;
25 }
26
27 void remove(Node node) {
28 node.prev.next = node.next;
29 node.next.prev = node.prev;
30 }
31
32 void pushFront(Node node) {
33 node.prev = head;
34 node.next = head.next;
35 head.next.prev = node;
36 head.next = node;
37 }
38
39 int get(int key) {
40 if (!cache.containsKey(key)) return -1;
41 Node node = cache.get(key);
42 remove(node);
43 pushFront(node);
44 return node.value;
45 }
46
47 void put(int key, int value) {
48 if (cache.containsKey(key)) {
49 Node node = cache.get(key);
50 node.value = value;
51 remove(node);
52 pushFront(node);
53 } else {
54 Node node = new Node(key, value);
55 cache.put(key, node);
56 pushFront(node);
57 if (cache.size() > capacity) {
58 Node lru = tail.prev;
59 remove(lru);
60 cache.remove(lru.key);
61 }
62 }
63 }
64 }
65
66 public static List<String> lruCache(int capacity, List<List<String>> instructions) {
67 LRUCacheImpl lruCache = new LRUCacheImpl(capacity);
68 List<String> output = new ArrayList<>();
69 for (List<String> instruction : instructions) {
70 String command = instruction.get(0);
71 if (command.equals("put")) {
72 lruCache.put(Integer.parseInt(instruction.get(1)), Integer.parseInt(instruction.get(2)));
73 } else if (command.equals("get")) {
74 output.add(String.valueOf(lruCache.get(Integer.parseInt(instruction.get(1)))));
75 }
76 }
77 return output;
78 }
79
80 public static List<String> splitWords(String s) {
81 return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
82 }
83
84 public static void main(String[] args) {
85 java.util.Scanner scanner = new java.util.Scanner(System.in);
86 int capacity = Integer.parseInt(scanner.nextLine());
87 int instructionsLength = Integer.parseInt(scanner.nextLine());
88 List<List<String>> instructions = new ArrayList<>();
89 for (int i = 0; i < instructionsLength; i++) {
90 instructions.add(splitWords(scanner.nextLine()));
91 }
92 scanner.close();
93 List<String> res = lruCache(capacity, instructions);
94 for (String line : res) {
95 System.out.println(line);
96 }
97 }
98}
991"use strict";
2
3class Node {
4 constructor(key, value) {
5 this.key = key;
6 this.value = value;
7 this.prev = null;
8 this.next = null;
9 }
10}
11
12class LRUCache {
13 constructor(capacity) {
14 this.capacity = capacity;
15 this.cache = new Map();
16 this.head = new Node(-1, -1);
17 this.tail = new Node(-1, -1);
18 this.head.next = this.tail;
19 this.tail.prev = this.head;
20 }
21
22 remove(node) {
23 node.prev.next = node.next;
24 node.next.prev = node.prev;
25 }
26
27 pushFront(node) {
28 node.prev = this.head;
29 node.next = this.head.next;
30 this.head.next.prev = node;
31 this.head.next = node;
32 }
33
34 get(key) {
35 if (!this.cache.has(key)) return -1;
36 const node = this.cache.get(key);
37 this.remove(node);
38 this.pushFront(node);
39 return node.value;
40 }
41
42 put(key, value) {
43 if (this.cache.has(key)) {
44 const node = this.cache.get(key);
45 node.value = value;
46 this.remove(node);
47 this.pushFront(node);
48 } else {
49 const node = new Node(key, value);
50 this.cache.set(key, node);
51 this.pushFront(node);
52 if (this.cache.size > this.capacity) {
53 const lru = this.tail.prev;
54 this.remove(lru);
55 this.cache.delete(lru.key);
56 }
57 }
58 }
59}
60
61function lruCache(capacity, instructions) {
62 const cache = new LRUCache(capacity);
63 const output = [];
64 for (const instruction of instructions) {
65 const [command, ...args] = instruction;
66 if (command === 'put') {
67 cache.put(parseInt(args[0]), parseInt(args[1]));
68 } else if (command === 'get') {
69 output.push(String(cache.get(parseInt(args[0]))));
70 }
71 }
72 return output;
73}
74
75function splitWords(s) {
76 return s === "" ? [] : s.split(" ");
77}
78
79function* main() {
80 const capacity = parseInt(yield);
81 const instructionsLength = parseInt(yield);
82 const instructions = [];
83 for (let i = 0; i < instructionsLength; i++) {
84 instructions.push(splitWords(yield));
85 }
86 const res = lruCache(capacity, instructions);
87 for (const line of res) {
88 console.log(line);
89 }
90}
91
92class EOFError extends Error {}
93{
94 const gen = main();
95 const next = (line) => gen.next(line).done && process.exit();
96 let buf = "";
97 next();
98 process.stdin.setEncoding("utf8");
99 process.stdin.on("data", (data) => {
100 const lines = (buf + data).split("\n");
101 buf = lines.pop();
102 lines.forEach(next);
103 });
104 process.stdin.on("end", () => {
105 buf && next(buf);
106 gen.throw(new EOFError());
107 });
108}
1091class Node {
2 key: number;
3 value: number;
4 prev: Node | null;
5 next: Node | null;
6
7 constructor(key: number, value: number) {
8 this.key = key;
9 this.value = value;
10 this.prev = null;
11 this.next = null;
12 }
13}
14
15class LRUCache {
16 private capacity: number;
17 private cache: Map<number, Node>;
18 private head: Node;
19 private tail: Node;
20
21 constructor(capacity: number) {
22 this.capacity = capacity;
23 this.cache = new Map();
24 this.head = new Node(-1, -1);
25 this.tail = new Node(-1, -1);
26 this.head.next = this.tail;
27 this.tail.prev = this.head;
28 }
29
30 private remove(node: Node): void {
31 node.prev!.next = node.next;
32 node.next!.prev = node.prev;
33 }
34
35 private pushFront(node: Node): void {
36 node.prev = this.head;
37 node.next = this.head.next;
38 this.head.next!.prev = node;
39 this.head.next = node;
40 }
41
42 get(key: number): number {
43 if (!this.cache.has(key)) return -1;
44 const node = this.cache.get(key)!;
45 this.remove(node);
46 this.pushFront(node);
47 return node.value;
48 }
49
50 put(key: number, value: number): void {
51 if (this.cache.has(key)) {
52 const node = this.cache.get(key)!;
53 node.value = value;
54 this.remove(node);
55 this.pushFront(node);
56 } else {
57 const node = new Node(key, value);
58 this.cache.set(key, node);
59 this.pushFront(node);
60 if (this.cache.size > this.capacity) {
61 const lru = this.tail.prev!;
62 this.remove(lru);
63 this.cache.delete(lru.key);
64 }
65 }
66 }
67}
68
69function lruCache(capacity: number, instructions: string[][]): string[] {
70 const cache = new LRUCache(capacity);
71 const output: string[] = [];
72 for (const instruction of instructions) {
73 const [command, ...args] = instruction;
74 if (command === 'put') {
75 cache.put(parseInt(args[0]), parseInt(args[1]));
76 } else if (command === 'get') {
77 output.push(String(cache.get(parseInt(args[0]))));
78 }
79 }
80 return output;
81}
82
83function splitWords(s: string): string[] {
84 return s === "" ? [] : s.split(" ");
85}
86
87function* main() {
88 const capacity = parseInt(yield);
89 const instructionsLength = parseInt(yield);
90 const instructions = [];
91 for (let i = 0; i < instructionsLength; i++) {
92 instructions.push(splitWords(yield));
93 }
94 const res = lruCache(capacity, instructions);
95 for (const line of res) {
96 console.log(line);
97 }
98}
99
100class EOFError extends Error {}
101{
102 const gen = main();
103 const next = (line?: string) => gen.next(line ?? "").done && process.exit();
104 let buf = "";
105 next();
106 process.stdin.setEncoding("utf8");
107 process.stdin.on("data", (data: string) => {
108 const lines = (buf + data).split("\n");
109 buf = lines.pop() ?? "";
110 lines.forEach(next);
111 });
112 process.stdin.on("end", () => {
113 buf && next(buf);
114 gen.throw(new EOFError());
115 });
116}
1171#include <algorithm>
2#include <iostream>
3#include <iterator>
4#include <limits>
5#include <sstream>
6#include <string>
7#include <vector>
8
9#include <string>
10#include <vector>
11#include <unordered_map>
12
13struct Node {
14 int key;
15 int value;
16 Node* prev;
17 Node* next;
18 Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
19};
20
21class LRUCache {
22public:
23 int capacity;
24 std::unordered_map<int, Node*> cache;
25 Node* head;
26 Node* tail;
27
28 LRUCache(int cap) : capacity(cap) {
29 head = new Node(-1, -1);
30 tail = new Node(-1, -1);
31 head->next = tail;
32 tail->prev = head;
33 }
34
35 void remove(Node* node) {
36 node->prev->next = node->next;
37 node->next->prev = node->prev;
38 }
39
40 void push_front(Node* node) {
41 node->prev = head;
42 node->next = head->next;
43 head->next->prev = node;
44 head->next = node;
45 }
46
47 int get(int key) {
48 if (cache.find(key) == cache.end()) return -1;
49 Node* node = cache[key];
50 remove(node);
51 push_front(node);
52 return node->value;
53 }
54
55 void put(int key, int value) {
56 if (cache.find(key) != cache.end()) {
57 Node* node = cache[key];
58 node->value = value;
59 remove(node);
60 push_front(node);
61 } else {
62 Node* node = new Node(key, value);
63 cache[key] = node;
64 push_front(node);
65 if ((int)cache.size() > capacity) {
66 Node* lru = tail->prev;
67 remove(lru);
68 cache.erase(lru->key);
69 delete lru;
70 }
71 }
72 }
73};
74
75std::vector<std::string> lru_cache(int capacity, std::vector<std::vector<std::string>> instructions) {
76 LRUCache lruCache(capacity);
77 std::vector<std::string> output;
78 for (const auto& instruction : instructions) {
79 const std::string& command = instruction[0];
80 if (command == "put") {
81 lruCache.put(std::stoi(instruction[1]), std::stoi(instruction[2]));
82 } else if (command == "get") {
83 output.push_back(std::to_string(lruCache.get(std::stoi(instruction[1]))));
84 }
85 }
86 return output;
87}
88
89void ignore_line() {
90 std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
91}
92
93template<typename T>
94std::vector<T> get_words() {
95 std::string line;
96 std::getline(std::cin, line);
97 std::istringstream ss{line};
98 ss >> std::boolalpha;
99 std::vector<T> v;
100 std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
101 return v;
102}
103
104int main() {
105 int capacity;
106 std::cin >> capacity;
107 ignore_line();
108 int instructions_length;
109 std::cin >> instructions_length;
110 ignore_line();
111 std::vector<std::vector<std::string>> instructions;
112 for (int i = 0; i < instructions_length; i++) {
113 instructions.emplace_back(get_words<std::string>());
114 }
115 std::vector<std::string> res = lru_cache(capacity, instructions);
116 for (const std::string& line : res) {
117 std::cout << line << '\n';
118 }
119}
1201class Node
2 attr_accessor :key, :value, :prev, :next
3 def initialize(key, value)
4 @key = key
5 @value = value
6 @prev = nil
7 @next = nil
8 end
9end
10
11class LRUCache
12 def initialize(capacity)
13 @capacity = capacity
14 @cache = {}
15 @head = Node.new(-1, -1)
16 @tail = Node.new(-1, -1)
17 @head.next = @tail
18 @tail.prev = @head
19 end
20
21 def remove(node)
22 node.prev.next = node.next
23 node.next.prev = node.prev
24 end
25
26 def push_front(node)
27 node.prev = @head
28 node.next = @head.next
29 @head.next.prev = node
30 @head.next = node
31 end
32
33 def get(key)
34 return -1 unless @cache.key?(key)
35 node = @cache[key]
36 remove(node)
37 push_front(node)
38 node.value
39 end
40
41 def put(key, value)
42 if @cache.key?(key)
43 node = @cache[key]
44 node.value = value
45 remove(node)
46 push_front(node)
47 else
48 node = Node.new(key, value)
49 @cache[key] = node
50 push_front(node)
51 if @cache.size > @capacity
52 lru = @tail.prev
53 remove(lru)
54 @cache.delete(lru.key)
55 end
56 end
57 end
58end
59
60def lru_cache(capacity, instructions)
61 cache = LRUCache.new(capacity)
62 output = []
63 instructions.each do |instruction|
64 command = instruction[0]
65 if command == "put"
66 cache.put(instruction[1].to_i, instruction[2].to_i)
67 elsif command == "get"
68 output << cache.get(instruction[1].to_i).to_s
69 end
70 end
71 output
72end
73
74if __FILE__ == $0
75 capacity = Integer(gets, 10)
76 instructions = Array.new(Integer(gets, 10)) { gets.split }
77 res = lru_cache(capacity, instructions)
78 res.each { |line| puts(line) }
79end
80Run and Test
Test 3 exercises the most important property: that get refreshes recency, not just put.
The capacity is 2. The sequence is put(1, 10), put(2, 20), get(1), put(3, 30),
then get(1), get(2), get(3).
After put(1) and put(2) the list is: head ↔ 2 ↔ 1 ↔ tail. Both slots are full. The
get(1) call promotes key 1 to the front: head ↔ 1 ↔ 2 ↔ tail. Now key 2 is the
least-recently-used entry. When put(3, 30) arrives, the cache is over capacity. It evicts
tail.prev, which is key 2. The list becomes: head ↔ 3 ↔ 1 ↔ tail.
The three gets that follow return 10, -1, 30 — key 1 survived because a read counted as
a use, key 2 was evicted because the read happened before it could be promoted, and key 3 is
the newest entry. This is the property the interviewer is checking: both operations refresh
recency, not just writes.
The sequence of list mutations makes the eviction concrete.
Concurrency and Thread Safety
A shared LRU cache is not thread-safe as written. Two concurrent get calls both promote their
respective nodes to the front, and without synchronisation they interleave the four pointer
assignments in _push_front, leaving the list corrupt. Because get mutates internal state
(the list order), it cannot hold a shared read-lock — it needs the same exclusive lock as put.
This means a naive lock-per-cache design serialises all reads, which limits throughput under
heavy concurrent access.
One approach is to shard the cache into N independent buckets, each with its own lock. Threads hash their key to a bucket and acquire only that bucket's lock, so unrelated keys never contend. The full analysis of that trade-off — including how to size N and how it interacts with memory — belongs in the key-value store case study.
Sharding reduces contention by partitioning keys across independent locks.
Extensions
TTL expiry is the most common follow-up. Each node gains a timestamp set at insertion or last
access. A lazy approach checks the timestamp on get and treats stale entries as misses, removing
them on the spot. An eager approach runs a background thread that periodically scans entries near
the tail (which are the oldest) and evicts any past their TTL.
LFU (least-frequently-used) eviction replaces the doubly-linked list with a frequency map: a dict from frequency count to a linked list of nodes at that count, plus a pointer to the current minimum frequency. On each access, the node moves from its current frequency bucket to the next — all still O(1). LFU eviction uses a different policy and is usually treated as a separate cache design.
A thread-safe wrapper is the lightest extension: a thin class that holds an LRUCache and a
threading.Lock, delegating every call to the inner cache inside a with self._lock block. This
works correctly at the cost of serialising all operations. Sharding, described above, is the next
step when that serialisation becomes the bottleneck.
Each extension slots in beside the existing design rather than requiring a rewrite of Node or
the two private helpers. That stability follows from isolating all pointer arithmetic in private
methods from the start, keeping the public interface to get and put.
Quiz
Test your understanding of the LRU Cache design decisions covered in this article.
LRU Cache Design Quiz
Why does the LRU Cache design combine a hash map with a doubly-linked list rather than using either structure alone?
Why must each Node store its own key, in addition to its value?
Why does get() move the accessed entry to the front of the list, rather than leaving it in place?
What happens when a put() call causes the cache to exceed its capacity, and which node is evicted?
How do sentinel head and tail nodes simplify the pointer surgery in _remove and _push_front?