常见缓存淘汰策略

  • 先进先出策 略FIFO(First In，First Out)
  • 最少使用策略LFU(Least Frequently Used)
  • 最近最少使用策略LRU(Least Recently Used)


数组 VS 链表

数组：需要连续的内存空间来存储，如果申请100M大小的数组，当内存中没有连续的、足够大的存储空间，会申请失败。
链表：不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用，所以如果我们申请的是100MB大小的链表，根本不会有问 题。 常见的链表有：单链表、双向链表和循环链表。

image.png

image.png

image.png

image.png

使用链表实现LRU

如何实现LRU缓存淘汰算法
答：使用有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。
插入新数据的时候有两种情况

  1. 缓存未满：直接插入链表头部
  2. 满了：删除尾部，插入头部

此时时间复杂度是 O(n)

链表常见问题：

单链表反转
链表中环的检测
两个有序的链表合并
删除链表倒数第n个结点
求链表的中间结点

链表逆序：https://www.jianshu.com/p/8b6f4dbe497e