• Paul Shan
    2022-01-13
    LRU需要把中间的节点移动到头部，并且要删除尾部节点，单链表对这两个操作都需要O(n),双链表可以用O(1)完成。LRU组合了哈希表和双向链表各自的强项，因而提供了快速的查询和灵活的资源管理两项功能。

    作者回复: 说的很对～

    
    2
  • liuchao90h
    2022-05-11
    其实严格来讲，因为用到了双向链表，所以最差时间复杂度应该是O(n)才对吧？虽然示例代码用了语言自带的包装，但不能忽视本身内部的损耗吧？再有就是作者无无语界确实博才，但对读者却走着更高的理解要求，虽然能猜出各语言大概含义，但阅读起来还是吃力些
    共 1 条评论
    1
  • 拓山
    2023-08-10 来自浙江
    维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。 1. 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。 2. 如果此数据没有在缓存链表中，又可以分为两种情况：如果此时缓存未满，则将此结点直接插入到链表的头部；如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。
    
    
  • 西门吹牛
    2022-01-22
    双向链表，插入删除更灵活，单向链表需要在遍历的过程中记录当前节点的前驱节点，然后前驱节点指直接next后继节点执行删除，双向链表直接找到删除的节点 node，直接 node.pre.next = node.next，node.next.pre = node.pre
    
    