大多数LRU缓存教程都强调使用双重链接列表和组合字典。该字典既包含链接列表上的相应节点的值，又有引用。
执行删除操作时，我们从字典中的链接列表中查找节点，我们必须删除它。
现在这是很奇怪的地方。大多数教程都认为我们需要前面的节点才能从链接列表中删除当前节点。这样做是为了获得o(1(时间。
但是，有一种方法可以从O(1(时间中的单个链接列表中删除节点。我们将当前节点的值设置为下一个节点，然后杀死下一个节点。
我的问题是：为什么所有这些教程都显示如何使用单链接列表来保存常数空间时如何实现LRU缓存？
您是正确的，可以使用单个链接列表，而不是双链接列表，如下所示：
标准方法是一个指向双链接列表的hashmap，以使删除变得容易。要使用单独的链接列表执行此操作，而无需使用O(n(搜索，请在链接列表中的前一个节点(您关心的一个的前身，或者如果元素位于前面(中的前一个节点(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解决方案如此常见？它更容易理解和使用。
如果优化是一个问题，那么单个链接列表的略微简单解决方案的权衡绝对值得。
交换有效载荷
有一些并发症- 有效载荷可能很大(例如缓冲区(
- 申请代码的一部分仍可以参考有效载荷(是否固定(
- 可能涉及锁或静音(可以由dll/hash节点和/或有效载荷 拥有(
在任何情况下，修改DLL最多都会影响2*2个指针，交换有效载荷将需要(swap 的memcpy(行走散布链(两次(，这可能需要访问结构中的任何节点。