为什么LRU缓存使用双链接列表而不是单链接列表？
我一直试图理解为什么LRU缓存使用双重链接列表而不是单一链接列表？
如果按时间复杂度计算，它们的插入、更新和删除都是相同的。这是备忘单
是因为DLL中的双向指针用于更容易地将节点移动到后部还是前部？？
共有2个答案
要从链接列表中删除目标节点，需要修改指向该节点的其他节点。
在双链接列表中，目标节点具有指向这些其他节点的指针，因此很容易找到它们。
在单链接列表中，目标节点没有指向它的另一个节点的指针。不过，您仍然需要修改该节点，因此您必须搜索它。
使用列表（DLL/SLL）实现LRU缓存背后的想法是将最近使用的页面（节点）移动到前面。
这涉及到大量的转移，比如节点在列表中间（DLL/SLL），你必须删除节点，重新排列上一个节点的下一个指针。
在这种情况下，如果我们使用单向链接列表，我们必须维护最近访问的节点的前一个节点。
如果我们使用双链表，这个操作是不必要的，因为它已经维护了上一个和下一个指针。
这里的问题是访问最新的节点，我们使用哈希表访问O（1）中的节点。
-
给定单链接列表：
-
我已经得到了实现双向链表的框架。我被PushFront（）方法难住了。方法应该将提供的元素添加到链表的前面，并且应该将地址返回到新的头节点。我对如何访问列表的当前头部感到困惑，以便我可以将其分配给pNext指针。到目前为止，PushTop（）方法看起来是这样的： 元素类构造函数： 数据类： 主要： 我的理解是，您通常会在调用PushFron（）时提供头的地址，但是因为我没有提供，我不确定如何访问它
-
大多数LRU缓存教程强调组合使用双向链表和字典。字典保存该值和对链表上相应节点的引用。 当我们执行删除操作时，我们从字典中的链表中查找节点，我们必须将其删除。 现在这里是它变得奇怪的地方。大多数教程认为，我们需要前面的节点才能从链表中删除当前节点。这样做是为了获得O（1）时间。 但是，这里有一种方法可以在O（1）时间内从单链接列表中删除节点。我们将当前节点的值设置为下一个节点，然后杀死下一个节点。
-
我目前无法获得双链接列表的反向函数来正确处理作业，我已经阅读了其他线程并在谷歌上搜索，但通常不同的是，我的问题以常量传递，它返回一个“dlist”。教授提供了一个“代码测试仪”，它说我的代码在执行“反向（反向（dlist c））”时，并不等于它本身就是“c”。[反转两次并不等于它本身]。 dlist类是： 这是反向函数： 每个数据列表节点都有一个指向前一个节点的指针和一个指向下一个节点的指针。dl
-
我使用的参考资料如下： 出于效率考虑，我们选择队列的前面位于列表的开头，队列的后面位于列表的末尾。这样，我们从头部移除，并在尾部插入。 我想知道为什么在头部插入并在尾巴上移除会不好？这是因为在单链表中，删除尾节点并不容易，因为您必须访问之前的节点，而在单链表中执行此操作的唯一方法是从头开始？
-
我试图初始化一个双链接列表，其中包含另一个双链接列表中的虚拟节点（也包含虚拟节点）。例如，学生列表中的一个节点有许多朋友存储在该节点内的链接列表中。这是我的代码： 当我试图编译它时，它告诉我：警告：来自不兼容指针类型的赋值。它出现在我发表评论的台词上。请帮忙^^ 编辑：谢谢鸭嘴兽！