数组实现lru缓存结构清晰、适合教学与资源受限场景，但get/put时间复杂度为o(n)；通过线性扫描定位、左移覆盖再前置实现访问更新，容量满时淘汰末尾元素。

用数组实现 LRU 缓存是理解其核心逻辑最直观的方式，适合教学、原型验证或轻量级场景。虽然性能不如链表+哈希表组合（O(n) 查找和移动），但结构清晰、无需额外指针管理，便于调试和嵌入资源受限环境。

数组 LRU 的基本结构设计

定义一个固定长度的数组，每个元素存储键值对（如 [key, value]），并维护当前有效元素数量。数组头部（索引 0）代表“最近访问”，尾部（最大索引）代表“最久未使用”。

• 初始化时数组为空，或用 null / undefined 占位
• 容量设为 capacity，实际最多存 capacity 个有效项
• 不依赖额外索引数组或哈希表，所有操作基于线性扫描

核心操作：get 时的位置更新逻辑

当调用 get(key) 且命中缓存时，需将对应项“提到最前面”。这涉及三步：

• 查找：从左到右遍历数组，找到第一个 item[0] === key 的位置 i
• 移出：将索引 i 处的元素取出，并把 i 右侧所有元素左移一位（覆盖原位置）
• 前置：将取出的元素插入到数组开头（索引 0），其余元素顺次后移；若数组未满，也可先清空末尾再整体右移，再填入开头

例如数组为 [[3,3], [2,2], [1,1]]（容量 3），执行 get(2) 后变为 [[2,2], [3,3], [1,1]]。

核心操作：put 时的插入与淘汰逻辑

put(key, value) 分两种情况处理：

• 已存在 key：同 get 逻辑，先定位、移出、再插到开头，并更新 value
• key 不存在：
  • 若当前元素数
  • 若已达 capacity：先删除尾部元素（即最久未使用的项），再将新项插入开头

注意：插入开头时，原有元素必须整体右移——这是数组实现的关键开销点，也是它不适合高频读写的主因。

边界与实用细节提醒

实战中容易忽略但影响稳定性的点：

• 数组长度始终固定，用 size 计数器跟踪有效项数，避免误删 null 占位符
• 查找失败时返回默认值（如 -1 或 undefined），不要抛异常，保持接口契约
• 插入开头前，确保尾部有空间：若 size === capacity，必须先淘汰（tail = array[size−1]）再腾位
• JavaScript 中可用 array.unshift() 和 array.splice(i, 1) 简化操作，但要注意 unshift 是 O(n) —— 这正是性能瓶颈所在

不复杂但容易忽略