⚡Flashcard Drill➔
NeetCode #338LC-146MediumLinked ListNC 150NC 250
← Back to All Problems

#338 · #146 · LRU Cache(LRU 缓存)

📌 Problem Statement & Constraints

Design a Least Recently Used (LRU) cache with a fixed capacity. Implement get(key) returning the value or -1, and put(key, value). Both must run in O(1) average time. When the capacity is exceeded, evict the least recently used key. Constraints: 1 <= capacity <= 3000; at most 2 * 10^5 calls.

💡 Core Algorithmic Approaches

  1. Two structures are needed: a hash map for O(1) lookup and a doubly linked list for O(1) recency updates.
  2. The list orders keys from most recently used (head) to least recently used (tail).
  3. get and put both move the touched key to the head; when full, put removes the tail.
  4. Python's OrderedDict implements exactly this, with move_to_end and popitem(last=False).

💻 Benchmark Python3 Implementation

class LRUCache:
    def __init__(self, capacity: int):
        from collections import OrderedDict
        self.cap = capacity
        self.d = OrderedDict()             # front = most recently used

    def get(self, key: int) -> int:
        if key not in self.d:
            return -1
        self.d.move_to_end(key)            # mark as recently used
        return self.d[key]

    def put(self, key: int, value: int) -> None:
        if key in self.d:
            self.d.move_to_end(key)        # refresh recency
        self.d[key] = value
        if len(self.d) > self.cap:
            self.d.popitem(last=False)     # evict the least recently used


# From-scratch doubly linked list, if OrderedDict is disallowed
class LRUCache2:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.map = {}
        self.head = {"prev": None, "next": None}   # sentinels
        self.tail = {"prev": self.head, "next": None}
        self.head["next"] = self.tail

    def _remove(self, node):
        node["prev"]["next"] = node["next"]
        node["next"]["prev"] = node["prev"]

    def _add_front(self, node):
        node["next"] = self.head["next"]
        node["prev"] = self.head
        self.head["next"]["prev"] = node
        self.head["next"] = node

    def get(self, key: int) -> int:
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._add_front(node)
        return node["val"]

    def put(self, key: int, value: int) -> None:
        if key in self.map:
            self._remove(self.map[key])
        node = {"key": key, "val": value, "prev": None, "next": None}
        self.map[key] = node
        self._add_front(node)
        if len(self.map) > self.cap:
            lru = self.tail["prev"]
            self._remove(lru)
            del self.map[lru["key"]]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(1) per operation for both variants: hash lookup plus a constant number of pointer updates.
💾 Space Complexity
O(capacity).

⚠️ Interview Pitfalls & Follow-ups

  • Using a plain dict: Python dicts preserve insertion order but provide no O(1) way to remove the least recently used entry by recency.
  • Forgetting to refresh recency on put of an existing key: the key would be evicted too early.
  • Evicting before inserting: the size check must happen after the insertion.
  • Using popitem() without last=False: that removes the most recently used item, the opposite of what is needed.
  • Using a singly linked list: removing an arbitrary node (needed for get) requires the previous pointer.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Linked List Problems

中文速览与面试要点

LRU 缓存

请你设计并实现一个满足 LRU(最近最少使用) 缓存约束的数据结构。实现 LRUCache 类: LRUCache(capacity) 以正整数容量初始化 LRU 缓存; get(key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 −1; put(key, value) 如果关键字 key 已经存在,则变更其数据值;如果不存在,则向缓存中插入该组 key-value。如果插入操作导致关键字数量超过 capacity,则应该 逐出 最久未使用的关键字。函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。约束:1 ≤ capacity ≤ 3000;0 ≤ key ≤ 10^4;0 ≤ value ≤ 10^5;最多调用 2 × 10^5 次 get 和 put。

核心要点

  • 哈希表 + 双向链表(标准解) :哈希表实现 O(1) 定位节点;双向链表维护访问顺序(头部为最近使用,尾部为最久未使用)。
  • 为什么必须双向 :删除节点时需要 O(1) 访问其前驱,单链表无法做到。
  • 哨兵头尾节点 : head (最近使用)与 tail (最久未使用)两个哑结点,可消除插入/删除时的边界判断。
  • 核心操作 :① _remove(node) 摘除节点;② _add(node) 把节点插到头部;③ get 时先删后加(移到头部);④ put 超出容量时删除 tail.prev 。

常见陷阱

  • 用单链表 :删除节点需要 O(n) 找前驱,无法满足 O(1)。必须双向。
  • 节点中不存 key :淘汰时只知道节点而不知道对应的 key,无法从哈希表中删除。必须在节点里保存 key。
  • get 时不更新访问顺序 : get 也是一次「使用」,必须把节点移到头部,否则 LRU 语义错误。
  • put 已存在的 key 时忘记更新 value 与顺序 :必须同时更新值和位置。
  • 淘汰时忘记从哈希表删除 :会导致哈希表与链表不一致。
  • 用 OrderedDict :Python 标准库可直接用 move_to_end 与 popitem(last=False) 实现,代码极短;面试中可先给手写版本再提这个。

参考实现

class ListNode:
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None


class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = {}                     # key -> 节点
        self.head = ListNode()              # 哨兵:最近使用端
        self.tail = ListNode()              # 哨兵:最久未使用端
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node: ListNode) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add(self, node: ListNode) -> None:
        """把节点插入到 head 之后(最近使用端)。"""
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._add(node)                     # 移到最近使用端
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.val = value
            self._remove(node)
            self._add(node)
            return
        if len(self.cache) >= self.cap:
            lru = self.tail.prev            # 最久未使用
            self._remove(lru)
            del self.cache[lru.key]
        node = ListNode(key, value)
        self.cache[key] = node
        self._add(node)