如何用链表实现LRU 缓存淘汰策略?

今天学习了链表(linked list)这个数据结构。学习链表有啥用呢?如何用链表来实现“LRU缓存淘汰算法”呢?思路是啥呢?。
LRU 是啥??
LRU(Least Recently Used)最近最少使用策略。缓存的容量是有限的
当缓存容量不足以存放需要缓存的新数据时,必须丢掉最不常用的缓存数据。

先来看看链表是啥吧

链表结构

以前因为好奇, 我跟着豆豆一起学过一些链表的基本概念,大概理解为:链表像是一个铁链子,一环扣一环。每一环也只知道自己的前后是谁。链表用一个next连接这自己的下一个元素。

好像这个概念和我们之前说的数组很像呢,确实很像,那有什么不一样的地方呢?
数组是可以任意访问的,但是链表要访问其中的第n 个元素的时候,只能从头开始找。这样,时间复杂度一直都是O(n) 链表不需要一个连续的存储空间,他的每个元素可以是零散的。如果内存不足的时候,申请一个超过内存的链表也是可以成功的,但是数组就不得行了。

  • 单链表
    我比较喜欢单链表,人家多单纯啊,只是单向的用next连接着自己的下一个元素。最后一个结点的 next指向null 就好了, 如果想给里面插入或者删掉数据的时候,很简单的做法就是直接改变相应的next 指针指向就好了。

  • 循环链表
    循环链表和单链表的区别就是最后一个next 指针指向第一个,这样就能形成一个单项的环。

  • 双向链表
    前面的单链表和循环链表都只是单向的,那么双向链接的区别就是除了有next,还会定义prev。这样每个item 不仅仅需要存储next ,还需要存储prev,这样肯定会更多的消耗空间,那它相对于单向的好处是什么呢?
    ``

  • 双向循环链表
    双向循环链表 就是双向链表 + 循环链表。两个特性的结合
    ``

从结构上来看,双向链表可以在O(1)的时间复杂度里面,找到前一个item。但是在单链表里面,需要重新再循环一次整个链表,时间复杂度就是O(n)

在实际的开发中,指定新增和指定删除的时候,双向链表的性能都要高于单向链表
相对于数组,链表更适用于更加频繁的插入,删除,和复杂度更高的场景。

如何基于链表实现 LRU 缓存淘汰算法?

基础思路是:

维护一个单向链表,越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时,我们从链表头开始顺序遍历链表。  
if 这个链表里,本身有这个item,那么就把这个item 从原来的位置删掉,然后插入到链表头的位置 
else 直接插入到头部(可能还需要兼容考虑此时缓存是否满)

我感觉用数组应该也是这个思路。只是实现方式不一样而已

今天又是学习理论知识的一天,期待实践s。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。