LeetCode 146. LRU 缓存设计与代码详解
LRU(Least Recently Used,最近最少使用)缓存机制是面试中高频出现的设计题,也是实际开发中常用的缓存策略(如浏览器缓存、Redis 的 LRU 淘汰策略)。LeetCode 146 题要求设计并实现满足 LRU 约束的数据结构,且 get 和 put 操作的平均时间复杂度必须为 O(1)。
一、题目回顾(明确需求)
实现 LRUCache 类,包含以下三个核心方法:
LRUCache(int capacity):以正整数作为容量 capacity 初始化 LRU 缓存。int get(int key):如果关键字 key 存在于缓存中,返回其对应的值;否则返回 -1。void put(int key, int value):如果 key 已存在,更新其 value;如果不存在,插入该 key-value。若插入后超出容量,逐出'最久未使用'的关键字。
核心约束:get 和 put 操作的平均时间复杂度必须为 O(1)。
二、核心思路分析(O(1) 复杂度的关键)
要实现 O(1) 的查找、插入和删除,单一数据结构无法满足,必须结合两种数据结构的优势:
- 哈希表(Map):用于存储 key 和对应的缓存节点,实现 O(1) 时间的查找(get 操作)和插入/删除(put 操作中更新 key)。
- 双向链表:用于维护缓存节点的'使用顺序'——最近使用的节点移到链表头部,最久未使用的节点留在链表尾部。这样逐出最久未使用节点时,直接删除链表尾部即可,实现 O(1) 删除;移动节点到头部也能通过调整指针实现 O(1) 操作。
补充说明:为什么用双向链表,而不是单向链表?
因为删除链表中的某个节点时,需要知道它的前驱节点,才能调整前驱节点的 next 指针。单向链表无法直接获取前驱节点,需要从头遍历,时间复杂度会变成 O(n),不符合要求;双向链表每个节点有 prev 和 next 指针,可直接定位前驱和后继,实现 O(1) 删除。
三、代码实现与逐部分详解
下面结合给出的 TypeScript 代码,逐部分拆解,搞懂每个类、每个方法的作用,以及细节处理。
3.1 定义缓存节点类(CacheItem)
双向链表的每个节点,需要存储 key、value,以及前驱(prev)和后继(next)指针,因此先定义一个 CacheItem 类封装节点信息。
class CacheItem {
key: number;
value: number;
prev: CacheItem | null;
next: CacheItem | null;
// 构造函数:初始化节点的 key、value,以及前驱、后继指针(默认 null)
constructor(key: number, value: number, prev: CacheItem | null = , : | = ) {
. = key;
. = value;
. = prev;
. = next;
}
}


