【一线大厂Java面试题合集】第62篇-高频数据结构面试题

第62篇：高频数据结构面试题模块：数据结构与算法 |难度：进阶 |面试频率：★★★★★1. 手写 LRU 缓存（HashMap + 双向链表）面试题：请手写一个 LRU（Least Recently Used）缓存，要求 get 和 put 操作都是 O(1)。算法思路LRU 是一种页面置换算法，核心思想是"最近最少使用的数据优先淘汰"。要实现 O(1) 的 get 和 put，需要组合两种数据结构：HashMap：存储 key 到双向链表节点的映射，实现 O(1) 查找。双向链表：维护访问顺序，最近访问的节点在头部，最久未访问的在尾部。双向链表可以在 O(1) 时间内完成节点删除和移动。操作流程：get(key)：从 HashMap 查到节点，将其移到链表头部，返回值。put(key, value)：若 key 存在，更新值并移到头部；若不存在，创建新节点插入头部，若超容量则删除尾部节点（同时从 HashMap 删除）。