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

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

1.如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。

2.如果此数据没有缓存在链表中，又可分为两种情况:

* 如果此时缓存未满，则将此节点直接插入到链表的头部;

*如果此时缓存已满，则链表尾结点删除，将新的数据结点插入到链表的头部

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

推荐阅读更多精彩内容