答案：LRU缓存通过字典和双向链表结合实现，字典提供O(1)查找，双向链表维护访问顺序，确保插入、删除和访问更新均为O(1)操作。每次get或put操作都会将对应节点移至链表头部，当缓存满时，尾部节点被移除，从而保证最久未使用项优先淘汰。虚拟头尾节点简化边界处理，而OrderedDict虽可替代实现，但自定义方式更利于理解底层机制。
在Python中实现LRU（Least Recently Used）缓存，核心思路在于巧妙地结合哈希表（Python的字典）和双向链表。字典确保我们能以O(1)的平均时间复杂度快速查找缓存中的任何项，而双向链表则负责维护项的访问顺序，使得最近使用的项总在链表头部，最久未使用的项（即待淘汰项）总在链表尾部，这样无论是更新访问顺序还是进行淘汰，都能保持高效。
解决方案
class Node:
"""双向链表节点定义"""
def __init__(self, key, value):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
"""
LRU缓存实现，结合字典和双向链表
"""
def __init__(self, capacity: int):
if capacity <= 0:
raise ValueError("缓存容量必须大于0")
self.capacity = capacity
self.cache = {} # 存储key到Node的映射，用于O(1)查找
self.head = Node(0, 0) # 虚拟头节点
self.tail = Node(0, 0) # 虚拟尾节点
self.head.next = self.tail
self.tail.prev = self.head
def _add_node(self, node):
"""将节点添加到链表头部（表示最近使用）"""
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def _remove_node(self, node):
"""从链表中移除指定节点"""
prev_node = node.prev
next_node = node.next
prev_node.next = next_node
next_node.prev = prev_node
def _move_to_head(self, node):
"""将已存在的节点移动到链表头部"""
self._remove_node(node)
self._add_node(node)
def get(self, key: int) -> int:
"""
获取缓存项。如果存在，将其移动到链表头部并返回其值；否则返回-1。
"""
if key not in self.cache:
return -1
node = self.cache[key]
self._move_to_head(node)
return node.value
def put(self, key: int, value: int) -> None:
"""
放入缓存项。
如果key已存在，更新其值并将其移动到链表头部。
如果key不存在：
如果缓存未满，创建新节点并添加到链表头部。
如果缓存已满，移除链表尾部（最久未使用）的节点，再添加新节点到头部。
"""
if key in self.cache:
node = self.cache[key]
node.value = value
self._move_to_head(node)
else:
new_node = Node(key, value)
self.cache[key] = new_node
self._add_node(new_node)
if len(self.cache) > self.capacity:
# 移除最久未使用的节点 (tail.prev)
lru_node = self.tail.prev
self._remove_node(lru_node)
del self.cache[lru_node.key]
LRU缓存为何偏爱双向链表而非普通列表？
在我看来，LRU缓存选择双向链表，这背后是性能和操作复杂度的深思熟虑。我们都知道，Python的
list在末尾添加（
append）和删除（
pop）通常是O(1)操作，但如果在中间或头部进行插入或删除，其时间复杂度就直接飙升到O(N)，因为需要移动后续所有元素。对于LRU缓存来说，每次访问一个元素，都需要将其“提升”到“最近使用”的位置，这通常意味着从当前位置删除，再插入到链表头部。如果用普通列表，这个“提升”操作会非常昂贵。
想象一下，我们缓存了1000个项目，突然访问了第500个。如果用普通列表，我们得先找到它（O(N)），然后删除它（O(N)），再把它加到列表开头（又是一个O(N)），这简直是性能灾难。而双向链表就不同了。每个节点都存储了指向前一个和后一个节点的引用。这意味着一旦我们通过字典以O(1)时间找到某个节点，我们就可以在O(1)时间内完成它的删除（只需修改它前后节点的
next和
prev指针）和插入（同样是修改几个指针）。这种效率上的巨大差异，正是双向链表在LRU实现中不可或缺的原因。它让我们的缓存操作，特别是“更新访问顺序”这一核心逻辑，保持了极高的效率。
如何处理缓存容量限制和淘汰策略？
处理LRU缓存的容量限制和淘汰策略，是整个实现的关键。我的做法是，在
LRUCache的
__init__方法中，我们首先设定一个
capacity。这个
capacity就是缓存能容纳的最大项目数。
立即学习“Python免费学习笔记（深入）”；
当
put方法被调用时，我们首先检查要插入的
key是否已经存在于
self.cache字典中。
狼群淘客 免费开源淘宝客程序
下载
狼群淘客系统基于canphp框架进行开发，MVC结构、数据库碎片式缓存机制，使网站支持更大的负载量，结合淘宝开放平台API实现的一个淘宝客购物导航系统采用php+mysql实现，任何人都可以免费下载使用 。狼群淘客的任何代码都是不加密的，你不用担心会有任何写死的PID，不用担心你的劳动成果被窃取。
-
如果
key
已存在：这表示我们只是更新一个现有项。在这种情况下，我们更新其value
，然后最关键的一步是调用_move_to_head
方法，将其对应的节点从链表当前位置移除，再添加到链表的头部。这反映了它刚刚被“使用”了，所以现在是最新的。 -
如果
key
不存在：这是一个全新的项。我们首先创建一个新的Node
，然后将其添加到self.cache
字典中，并调用_add_node
方法将其添加到链表的头部。 紧接着，我们就需要检查缓存是否“超载”了。我们通过len(self.cache) > self.capacity
来判断当前缓存中的项目数量是否超过了设定的capacity
。如果超载了，这意味着我们必须淘汰一个项目来为新项目腾出空间。LRU的策略是淘汰“最久未使用的”项目。在我们的双向链表中，这个项目就是紧挨着虚拟尾节点self.tail
的前一个节点（即self.tail.prev
）。我们称之为lru_node
。我们调用_remove_node(lru_node)
将其从链表中移除，然后通过del self.cache[lru_node.key]
将其从字典中也删除，完成彻底的淘汰。
这种机制确保了缓存始终在容量限制内运行，并且每次淘汰都严格遵循了“最久未使用”的原则。虚拟头尾节点的设计，更是简化了链表边缘情况的处理，让代码逻辑更清晰。
Python内置的OrderedDict
能否替代自定义LRU实现？
当然可以，而且在很多简单场景下，使用Python标准库
collections模块中的
OrderedDict来实现LRU缓存会显得非常简洁高效。
OrderedDict本身就维护了键值对的插入顺序。它的
move_to_end方法和在插入时检查容量并删除最老项的机制，与LRU缓存的逻辑高度契合。
一个基于
OrderedDict的LRU实现大致会是这样：
from collections import OrderedDict
class LRUCacheOrderedDict:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = OrderedDict()
def get(self, key: int) -> int:
if key not in self.cache:
return -1
self.cache.move_to_end(key) # 将key移动到末尾，表示最近使用
return self.cache[key]
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.cache.move_to_end(key) # 存在则移动到末尾
self.cache[key] = value # 更新或添加
if len(self.cache) > self.capacity:
self.cache.popitem(last=False) # 移除最老（最久未使用）的项这种实现方式确实非常优雅，代码量大大减少，并且由于
OrderedDict是用C实现的，其内部操作通常效率很高。
不过，话说回来，尽管
OrderedDict能很好地完成任务，但它也隐藏了LRU缓存底层双向链表的精妙机制。对于初学者或者需要深入理解数据结构和算法的开发者来说，自己动手实现一个基于字典和双向链表的LRU缓存，就像我们前面做的那样，其教育价值是
OrderedDict无法替代的。它能让我们更清晰地看到每个操作是如何影响底层数据结构的，以及为什么这些数据结构的选择如此关键。在面试或者需要对性能有极致掌控的场景下，理解并能手写底层逻辑，往往比仅仅会用库函数更能体现技术深度。所以，选择哪种方式，最终还是取决于具体的需求：追求简洁快速就用
OrderedDict，追求深入理解和精细控制则倾向于自定义实现。
