linked-list - 单向链表的 LRU 缓存

Question

大多数 LRU 缓存教程都强调结合使用双向链表和字典。该字典包含值和对链表上相应节点的引用。

当我们执行删除操作时，我们从字典中的链表中查找节点，我们必须删除它。

这就是它变得奇怪的地方。大多数教程认为我们需要前面的节点才能从链表中删除当前节点。这样做是为了获得 O(1) 时间。

但是，有一种方法可以在 O(1) 时间内从单链表中删除一个节点 here .我们将当前节点的值设置为下一个节点，然后杀死下一个节点。

我的问题是:为什么所有这些教程都展示了如何使用双向链表实现 LRU 缓存，而我们可以通过使用单向链表来节省常量空间？

Answer 1

你说的对，可以用单链表代替双链表，可见here :

标准方法是一个指向双向链表的 HashMap ，以便于删除。要在不使用 O(n) 搜索的情况下使用单链表执行此操作，请将 hashmap 指向链表中的前一个节点(您关心的节点的前身，如果元素位于前面则为 null)。

Retrieve list node:
hashmap(key) ? hashmap(key)->next : list.head

Delete:
successornode = hashmap(key)->next->next
hashmap( successornode ) = hashmap(key)
hashmap(key)->next = successornode
hashmap.delete(key)

为什么双向链表在 LRU 解决方案中如此普遍？更易于理解和使用。

如果优化是一个问题，那么单链表的稍微不那么简单的解决方案的权衡绝对值得。