LRU 缓存与链表：大厂面试最爱考的数据结构题

如果你准备过技术面试，大概率见过这道题：设计一个 LRU（最近最少使用）缓存，要求查询、插入、淘汰都在 O(1)。它看似简单，却精准考察了对链表和哈希表组合的掌握——而这正是必学必会算法轨道里尚未补齐的 C3 链表 节点的现实用武之地。

LRU 的规则是：缓存满了，就扔掉"最久没被用过"的那条。这就需要一个能快速把任意节点移到队首（刚用过）、并快速删除队尾（最久未用）的结构——双向链表恰好胜任：每个节点有前驱、后继指针，插入/删除都是 O(1)，不需要像数组那样搬移后半段。

但链表有个弱点：你不能 O(1) 知道"某个键在哪个节点"。于是再加一张哈希表，键映射到链表节点指针。查找时哈希 O(1) 定位节点，链表 O(1) 调整次序。两者合力，三个操作全部 O(1)。这道题的精髓，就是用对的数据结构各司其职、互补短板。

为什么面试官爱考它？因为它浓缩了算法设计的典型思维：单一结构都有缺陷，组合结构才能同时满足多个约束。链表解决"有序移动"，哈希解决"快速定位"，缺一个都不行。这也呼应了入门节里那句话——算法与数据结构是一体两面。

顺带一提，LRU 不只存在于面试题：操作系统页置换、Redis 的 maxmemory 策略、浏览器前进后退，底层都是类似思想。把链表学扎实（C3 节点），这类"组合题"就不再是拦路虎。

关联推荐

• GPT-5.6 递归自我改进 — 系统设计与递归思维的交汇
• （本批「算法与问题求解入门」KU 发布后回填互链）