带数组的 LRU - 研发

Question

为什么LRU使用链表？我们不能用数组来存储项目吗，所以最常用的项目将存储在数组的前面&至少在数组的最后。

我能想到不使用数组的唯一原因是，当 removing/updating 数组时，它的性能低于链表。

还有什么理由吗？

注意：- 此问题是出于学术目的或研究目的，以便更好地了解 LRU。

Answer 1

一些上下文：LRU 缓存是一种自定义数据结构，它保存 least r最近 used 快速访问的结果（这是有道理的，因为以消息传递应用程序为例——你不想等待 30 秒才能打开聊天，你想要最后 10 秒消息立即出现，如果你想得到更远的东西，那么你可以从数据库中获取它并等待）。

既然你已经提醒了这个重要的上下文，我们就可以了解为什么要使用链表了：

它通常会给出恒定的 insertion/deletion 时间，因为您知道要 insert/delete 的内容（您通常会在恒定时间内获得 HashMap）。如果你必须不断地 insert/delete 到一个数组，数组调整大小（O(N)）将对性能非常不利（记住我们不希望聊天消息永远加载），同时从链表中删除就像：

public void deleteNode(ListNode node) {
    node.val = node.next.val;
    node.next = node.next.next;
}

您可以使用数组，只是效率不高 — 然而还有更多使用链表的理由：我们想保留一个结构 其中（在恒定时间内）我们可以将 最近使用的 请求列表节点添加到链表的前面（在 head/sentinel 虚拟节点之后）。这允许你有一个恒定的时间 get() 方法。

带数组的 LRU - 研发

LRU with arrays - R&D

lru

data-structures