如何实现LRU缓存淘汰算法

image.png

原理

LRU：Least recently used，最近最少使用。缓存算法根据数据最近被访问的情况来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

算法实现

链表实现LRU缓存淘汰策略

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

如果，被访问的数据之前已经被缓存到链表中，遍历得到这个数据相对应的节点，并将其从原来的位置删除，然后插入到链表头部。

当被访问的数据没有存储在缓存的链表中时，并且链表中缓存未满，直接将数据插入链表表头。

当被访问的数据没有存储在缓存的链表中时，并且链表中缓存已满，则删除链表的尾部节点，将新的数据节点插入到链表的头部。