LeetCode 146: LRU Cache (Hash Map + Doubly Linked List)
LeetCode 146DesignHash TableLinked ListToday we solve LeetCode 146 - LRU Cache.
Source: https://leetcode.com/problems/lru-cache/
English
Problem Summary
Design a data structure that supports get(key) and put(key, value) in O(1) average time, with a fixed capacity. When capacity is exceeded, remove the least recently used entry.
Key Insight
Use Hash Map + Doubly Linked List: the map gives O(1) node lookup by key, and the linked list keeps usage order so we can move recently-used nodes to the front and evict from the back in O(1).
Brute Force and Limitations
A simple array/list can store entries, but updating recency requires searching and moving elements, which is O(n). This fails the strict O(1) requirement.
Optimal Algorithm Steps
1) Maintain dummy head and tail for a doubly linked list (most recent near head, least recent near tail).
2) Keep map[key] = node for direct access.
3) get(key): if missing return -1; otherwise move node to head and return value.
4) put(key, value): if key exists, update value and move node to head.
5) If key does not exist, insert new node at head and store in map.
6) If size exceeds capacity, remove node before tail (LRU) and delete its key from map.
Complexity Analysis
Time: O(1) average for both get and put.
Space: O(capacity).
Common Pitfalls
- Forgetting to move a node to MRU position after get.
- Updating existing key but not refreshing recency.
- Incorrect pointer unlink/link order causing broken list.
- Not removing evicted key from map, causing stale references.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class LRUCache {
private static class Node {
int key, value;
Node prev, next;
Node(int k, int v) { key = k; value = v; }
}
private final int capacity;
private final java.util.Map<Integer, Node> map = new java.util.HashMap<>();
private final Node head = new Node(0, 0);
private final Node tail = new Node(0, 0);
public LRUCache(int capacity) {
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}
public int get(int key) {
Node node = map.get(key);
if (node == null) return -1;
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
Node node = map.get(key);
if (node != null) {
node.value = value;
moveToHead(node);
return;
}
Node newNode = new Node(key, value);
map.put(key, newNode);
addAfterHead(newNode);
if (map.size() > capacity) {
Node lru = removeTail();
map.remove(lru.key);
}
}
private void moveToHead(Node node) {
remove(node);
addAfterHead(node);
}
private void addAfterHead(Node node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void remove(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private Node removeTail() {
Node node = tail.prev;
remove(node);
return node;
}
}type Node struct {
key, value int
prev, next *Node
}
type LRUCache struct {
cap int
m map[int]*Node
head *Node
tail *Node
}
func Constructor(capacity int) LRUCache {
head, tail := &Node{}, &Node{}
head.next = tail
tail.prev = head
return LRUCache{cap: capacity, m: make(map[int]*Node), head: head, tail: tail}
}
func (c *LRUCache) Get(key int) int {
node, ok := c.m[key]
if !ok {
return -1
}
c.moveToHead(node)
return node.value
}
func (c *LRUCache) Put(key int, value int) {
if node, ok := c.m[key]; ok {
node.value = value
c.moveToHead(node)
return
}
node := &Node{key: key, value: value}
c.m[key] = node
c.addAfterHead(node)
if len(c.m) > c.cap {
lru := c.removeTail()
delete(c.m, lru.key)
}
}
func (c *LRUCache) moveToHead(node *Node) {
c.remove(node)
c.addAfterHead(node)
}
func (c *LRUCache) addAfterHead(node *Node) {
node.prev = c.head
node.next = c.head.next
c.head.next.prev = node
c.head.next = node
}
func (c *LRUCache) remove(node *Node) {
node.prev.next = node.next
node.next.prev = node.prev
}
func (c *LRUCache) removeTail() *Node {
node := c.tail.prev
c.remove(node)
return node
}class LRUCache {
struct Node {
int key, value;
Node *prev, *next;
Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
int capacity;
unordered_map<int, Node*> mp;
Node *head, *tail;
void remove(Node* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
void addAfterHead(Node* node) {
node->prev = head;
node->next = head->next;
head->next->prev = node;
head->next = node;
}
void moveToHead(Node* node) {
remove(node);
addAfterHead(node);
}
Node* removeTail() {
Node* node = tail->prev;
remove(node);
return node;
}
public:
LRUCache(int cap) : capacity(cap) {
head = new Node(0, 0);
tail = new Node(0, 0);
head->next = tail;
tail->prev = head;
}
int get(int key) {
if (!mp.count(key)) return -1;
Node* node = mp[key];
moveToHead(node);
return node->value;
}
void put(int key, int value) {
if (mp.count(key)) {
Node* node = mp[key];
node->value = value;
moveToHead(node);
return;
}
Node* node = new Node(key, value);
mp[key] = node;
addAfterHead(node);
if ((int)mp.size() > capacity) {
Node* lru = removeTail();
mp.erase(lru->key);
delete lru;
}
}
};class Node:
def __init__(self, key=0, value=0):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.map = {}
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node: Node) -> None:
node.prev.next = node.next
node.next.prev = node.prev
def _add_after_head(self, node: Node) -> None:
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def _move_to_head(self, node: Node) -> None:
self._remove(node)
self._add_after_head(node)
def _remove_tail(self) -> Node:
node = self.tail.prev
self._remove(node)
return node
def get(self, key: int) -> int:
if key not in self.map:
return -1
node = self.map[key]
self._move_to_head(node)
return node.value
def put(self, key: int, value: int) -> None:
if key in self.map:
node = self.map[key]
node.value = value
self._move_to_head(node)
return
node = Node(key, value)
self.map[key] = node
self._add_after_head(node)
if len(self.map) > self.capacity:
lru = self._remove_tail()
del self.map[lru.key]class Node {
constructor(key = 0, value = 0) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}
var LRUCache = function(capacity) {
this.capacity = capacity;
this.map = new Map();
this.head = new Node();
this.tail = new Node();
this.head.next = this.tail;
this.tail.prev = this.head;
};
LRUCache.prototype._remove = function(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
};
LRUCache.prototype._addAfterHead = function(node) {
node.prev = this.head;
node.next = this.head.next;
this.head.next.prev = node;
this.head.next = node;
};
LRUCache.prototype._moveToHead = function(node) {
this._remove(node);
this._addAfterHead(node);
};
LRUCache.prototype._removeTail = function() {
const node = this.tail.prev;
this._remove(node);
return node;
};
LRUCache.prototype.get = function(key) {
if (!this.map.has(key)) return -1;
const node = this.map.get(key);
this._moveToHead(node);
return node.value;
};
LRUCache.prototype.put = function(key, value) {
if (this.map.has(key)) {
const node = this.map.get(key);
node.value = value;
this._moveToHead(node);
return;
}
const node = new Node(key, value);
this.map.set(key, node);
this._addAfterHead(node);
if (this.map.size > this.capacity) {
const lru = this._removeTail();
this.map.delete(lru.key);
}
};中文
题目概述
实现一个容量固定的 LRU 缓存，支持 get(key) 和 put(key, value)，并要求平均时间复杂度为 O(1)。容量超限时要淘汰最近最少使用的键值对。
核心思路
使用哈希表 + 双向链表：哈希表负责 O(1) 定位节点，双向链表负责维护访问顺序（头部是最新，尾部是最久未使用）。
暴力解法与不足
如果只用数组或普通列表，每次访问后都要线性移动元素，时间复杂度退化到 O(n)，不满足题目要求。
最优算法步骤
1）准备带哨兵的双向链表 head 和 tail。
2）维护 map[key] = node 快速查找。
3）get 命中后把节点移动到头部，并返回值。
4）put 如果键已存在：更新值并移动到头部。
5）若键不存在：新建节点插到头部，同时写入 map。
6）若超出容量：删除尾部前一个节点（LRU），并从 map 中移除该 key。
复杂度分析
时间复杂度：O(1)（平均）用于 get 和 put。
空间复杂度：O(capacity)。
常见陷阱
- get 后忘记更新“最近使用”顺序。
- 更新已有 key 时没有移动到头部。
- 双向链表断链（指针更新顺序错误）。
- 淘汰后未从哈希表删除，导致脏引用。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class LRUCache {
private static class Node {
int key, value;
Node prev, next;
Node(int k, int v) { key = k; value = v; }
}
private final int capacity;
private final java.util.Map<Integer, Node> map = new java.util.HashMap<>();
private final Node head = new Node(0, 0);
private final Node tail = new Node(0, 0);
public LRUCache(int capacity) {
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}
public int get(int key) {
Node node = map.get(key);
if (node == null) return -1;
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
Node node = map.get(key);
if (node != null) {
node.value = value;
moveToHead(node);
return;
}
Node newNode = new Node(key, value);
map.put(key, newNode);
addAfterHead(newNode);
if (map.size() > capacity) {
Node lru = removeTail();
map.remove(lru.key);
}
}
private void moveToHead(Node node) {
remove(node);
addAfterHead(node);
}
private void addAfterHead(Node node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void remove(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private Node removeTail() {
Node node = tail.prev;
remove(node);
return node;
}
}type Node struct {
key, value int
prev, next *Node
}
type LRUCache struct {
cap int
m map[int]*Node
head *Node
tail *Node
}
func Constructor(capacity int) LRUCache {
head, tail := &Node{}, &Node{}
head.next = tail
tail.prev = head
return LRUCache{cap: capacity, m: make(map[int]*Node), head: head, tail: tail}
}
func (c *LRUCache) Get(key int) int {
node, ok := c.m[key]
if !ok {
return -1
}
c.moveToHead(node)
return node.value
}
func (c *LRUCache) Put(key int, value int) {
if node, ok := c.m[key]; ok {
node.value = value
c.moveToHead(node)
return
}
node := &Node{key: key, value: value}
c.m[key] = node
c.addAfterHead(node)
if len(c.m) > c.cap {
lru := c.removeTail()
delete(c.m, lru.key)
}
}
func (c *LRUCache) moveToHead(node *Node) {
c.remove(node)
c.addAfterHead(node)
}
func (c *LRUCache) addAfterHead(node *Node) {
node.prev = c.head
node.next = c.head.next
c.head.next.prev = node
c.head.next = node
}
func (c *LRUCache) remove(node *Node) {
node.prev.next = node.next
node.next.prev = node.prev
}
func (c *LRUCache) removeTail() *Node {
node := c.tail.prev
c.remove(node)
return node
}class LRUCache {
struct Node {
int key, value;
Node *prev, *next;
Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
int capacity;
unordered_map<int, Node*> mp;
Node *head, *tail;
void remove(Node* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
void addAfterHead(Node* node) {
node->prev = head;
node->next = head->next;
head->next->prev = node;
head->next = node;
}
void moveToHead(Node* node) {
remove(node);
addAfterHead(node);
}
Node* removeTail() {
Node* node = tail->prev;
remove(node);
return node;
}
public:
LRUCache(int cap) : capacity(cap) {
head = new Node(0, 0);
tail = new Node(0, 0);
head->next = tail;
tail->prev = head;
}
int get(int key) {
if (!mp.count(key)) return -1;
Node* node = mp[key];
moveToHead(node);
return node->value;
}
void put(int key, int value) {
if (mp.count(key)) {
Node* node = mp[key];
node->value = value;
moveToHead(node);
return;
}
Node* node = new Node(key, value);
mp[key] = node;
addAfterHead(node);
if ((int)mp.size() > capacity) {
Node* lru = removeTail();
mp.erase(lru->key);
delete lru;
}
}
};class Node:
def __init__(self, key=0, value=0):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.map = {}
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node: Node) -> None:
node.prev.next = node.next
node.next.prev = node.prev
def _add_after_head(self, node: Node) -> None:
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def _move_to_head(self, node: Node) -> None:
self._remove(node)
self._add_after_head(node)
def _remove_tail(self) -> Node:
node = self.tail.prev
self._remove(node)
return node
def get(self, key: int) -> int:
if key not in self.map:
return -1
node = self.map[key]
self._move_to_head(node)
return node.value
def put(self, key: int, value: int) -> None:
if key in self.map:
node = self.map[key]
node.value = value
self._move_to_head(node)
return
node = Node(key, value)
self.map[key] = node
self._add_after_head(node)
if len(self.map) > self.capacity:
lru = self._remove_tail()
del self.map[lru.key]class Node {
constructor(key = 0, value = 0) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}
var LRUCache = function(capacity) {
this.capacity = capacity;
this.map = new Map();
this.head = new Node();
this.tail = new Node();
this.head.next = this.tail;
this.tail.prev = this.head;
};
LRUCache.prototype._remove = function(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
};
LRUCache.prototype._addAfterHead = function(node) {
node.prev = this.head;
node.next = this.head.next;
this.head.next.prev = node;
this.head.next = node;
};
LRUCache.prototype._moveToHead = function(node) {
this._remove(node);
this._addAfterHead(node);
};
LRUCache.prototype._removeTail = function() {
const node = this.tail.prev;
this._remove(node);
return node;
};
LRUCache.prototype.get = function(key) {
if (!this.map.has(key)) return -1;
const node = this.map.get(key);
this._moveToHead(node);
return node.value;
};
LRUCache.prototype.put = function(key, value) {
if (this.map.has(key)) {
const node = this.map.get(key);
node.value = value;
this._moveToHead(node);
return;
}
const node = new Node(key, value);
this.map.set(key, node);
this._addAfterHead(node);
if (this.map.size > this.capacity) {
const lru = this._removeTail();
this.map.delete(lru.key);
}
};
Comments