数据结构：缓存淘汰策略

文章目录
三种缓存淘汰策略单链表实现LRU数组实现LRU

三种缓存淘汰策略
1.FIFO - First In First Out - 先进先出 2.LFU - Least Frequently Used - 最少 - 使用 3.LRU - Least Recently Used - 最近 - 最少 - 使用

其中LRU使用最广，下面介绍 使用 链表 和 数组 来实现LRU

单链表实现LRU
（1）当访问的数据 - 没有存在 - 于存储缓存的链表中时： i- 如果缓存链表没满：将数据插入链表表头，时间复杂度为 O(1)； ii - 如果缓存链表满了：删除链表的末位，将新数据添加到 缓存链表 的表头，时间复杂度为 O(1)。
（2）当访问的数据 - 存在于 - 存储缓存的链表中时： 将该数据对应的节点，调整到链表表头，时间复杂度为 O(1)。
缓存链表满，从链表尾部开始清理

数据结构：缓存淘汰策略最先出现在Python成神之路。