LRUCache实现中为何self.left.next为LRU节点并需淘汰

我正在学习LeetCode中等题「LRU缓存」的最优解，对其中的解决方案代码里的LRU淘汰部分有疑问：为什么要删除LRU节点？或者说，为什么self.left.next代表最近最少使用（LRU）的键？比如当容量为2，双向链表经过操作后已有[1,1]和[2,2]两个节点，新增[3,3]后链表变为left <-> [2,2] <-> [1,1] <-> [3,3] <-> right，此时超出容量限制需删除LRU节点[2,2]，为什么self.left.next对应的是[2,2]而非[1,1]？

原代码实现 #

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


class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = {}  # 用哈希表映射key到对应节点

        # 初始化两个哨兵节点，简化链表首尾操作
        self.left, self.right = Node(0, 0), Node(0, 0)
        self.left.next, self.right.prev = self.right, self.left

    # 从链表中移除指定节点
    def remove(self, node):
        prev, nxt = node.prev, node.next
        prev.next, nxt.prev = nxt, prev

    # 将节点插入到链表最右侧（最近使用区）
    def insert(self, node):
        prev, nxt = self.right.prev, self.right
        prev.next = nxt.prev = node
        node.next, node.prev = nxt, prev

    def get(self, key: int) -> int:
        if key in self.cache:
            # 访问节点后，将其移到最近使用区
            self.remove(self.cache[key])
            self.insert(self.cache[key])
            return self.cache[key].val
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            # 存在则先移除旧节点
            self.remove(self.cache[key])
        # 创建新节点并插入到最近使用区
        self.cache[key] = Node(key, value)
        self.insert(self.cache[key])

        if len(self.cache) > self.cap:
            # 超出容量，删除LRU节点
            lru = self.left.next
            self.remove(lru)
            del self.cache[lru.key]

疑问解答 #

1. 为什么要删除LRU节点？

LRU缓存的核心规则就是当缓存容量已满时，删除最近最少被使用的节点。这么做的目的是让缓存优先保留近期频繁访问的数据，符合缓存“提升热点数据访问效率”的设计目标，避免缓存被冷数据占满。

2. 为什么self.left.next是LRU节点？

这个实现用了**两个哨兵节点（left和right）**来简化链表的首尾操作，同时约定了明确的节点顺序规则：

• 链表的最右侧（靠近right哨兵的一端）是最近使用（MRU）的节点：任何节点被新增（put）或访问（get）时，都会被移到这个位置（通过insert方法）。
• 链表的最左侧（靠近left哨兵的一端）是最久未使用（LRU）的节点：那些从未被访问、或者最早被访问后再也没碰过的节点，会一直停留在left哨兵的下一个位置，成为LRU节点。

结合你的例子详细走流程

假设你的操作顺序是：put(1,1) → put(2,2) → get(1) → put(3,3)

1. put(1,1)：缓存添加[1,1]节点，插入到right哨兵前，链表变为：left <-> [1,1] <-> right
2. put(2,2)：缓存添加[2,2]节点，插入到right哨兵前，链表变为：left <-> [1,1] <-> [2,2] <-> right
3. get(1)：找到[1,1]节点，先从链表中移除它，再插入到right哨兵前，链表变为：left <-> [2,2] <-> [1,1] <-> right。此时[1,1]成为最近使用的节点，[2,2]则是最久未被使用的节点。
4. put(3,3)：缓存添加[3,3]节点，插入到right哨兵前，链表变为：left <-> [2,2] <-> [1,1] <-> [3,3] <-> right。此时缓存长度达到3，超过容量2，所以取self.left.next（也就是[2,2]这个LRU节点），删除它并从缓存哈希表中移除。

这就是为什么你的例子里self.left.next对应的是[2,2]而非[1,1]——因为[1,1]在被访问后已经被移到了最近使用区，而[2,2]留在了最左侧，成为最久未使用的节点。

内容的提问来源于stack exchange，提问作者PineNuts0