【每日阅读】2021年5月11日-使用链表如何实现LRU缓存淘汰算法?

有疑问就留言给我吧😄

索引

其他

今天蛋壳的果加密码锁到期了,室友帮忙打开了外门锁,但是我卧室的门锁依旧打不开😂。因为蛋壳已经倒闭了,所以蛋壳客服联系不到无法解决,而且蛋壳app也登陆不上。然后我想联系果加客服,官网的电话竟然都是空号,服了,看来这果加也是个小品牌,是不是也已经倒闭了。最后只能叫开锁啦!这笔钱一定要从房东那要回来。开锁小哥上门速度很快,十几分钟就到了,花了大概3分钟就把锁钻了个洞然后把门打开了,不错。

正题

我们维护一个有序单链表,越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时,我们从链表头开始顺序遍历链表。

  1. 如果此数据之前已经被缓存在链表中了,我们遍历得到这个数据对应的结点,并将其从原来的位置删除,然后再插入到链表的头部。
  2. 如果此数据没有在缓存链表中,又可以分为两种情况:如果此时缓存未满,则将此结点直接插入到链表的头部;如果此时缓存已满,则链表尾结点删除,将新的数据结点插入链表的头部。

原创文章,作者:geekgao,如若转载,请注明出处:https://www.geekgao.cn/archives/2995

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

GitHub
分享本页
返回顶部