如何用链表实现LRU缓存淘汰算法

一、 缓存

1.1缓存介绍

缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比如常见的 CPU 缓存、数据库缓存、浏览器缓存等等

1.2 缓存策略

• 大小有限，当缓存被用满时，哪些数据应该被清理掉，哪些数据又应该保留呢?
• 先进先出策略 FIFO
• 最少使用策略 LFU
• 最近最少使用策略LRU

二、链表结构

2.1 单链表

数组结构和链表结构对比

• 数组需要一块连续的内存空间来存储，对内存的要求比较高
• 链表并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用
  
  单链表
  链表通过指针将一组零散的内存块串联在一起。把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。如图所示，记录下个结点地址的指针叫作后继指针 next
  

2.2 循环链表

循环链表是一种特殊的单链表。它跟单链表唯一的区别就在尾结点。单链表的尾结点指针指向空地址，表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。

2.3 双向链表

单向链表只有一个方向，结点只有一个后继指针 next 指向后面的结点。而双向链表，顾名思义，它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点

2.4 双向循环链表

2.5 链表与数组性能对比

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

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

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

• 如果此数据没有在缓存链表中，又可以分为两种情况：

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

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