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;
}
}
