常见的策略:

  • FIFO
  • LFU
  • LRU

五花八门的链表结构

数组与链表在存储结构上的比较:

image.png

单链表

image.png

链表的插入和删除操作:

  • O(1)

image.png

随机访问的性能:

  • O(n)

循环链表

image.png

双向链表

image.png

特点:

  • O(1) 复杂度寻找前驱节点

双向循环链表

image.png

链表 VS 数组性能大比拼

image.png

  • 数组简单易用，在实现上使用的是连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读。
  • 链表本身没有大小的限制，天然地支持动态扩容

如果你的代码对内存的使用非常苛刻，那数组就更适合你。因为链表中的每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针，所以内存消耗会翻倍。

对链表进行频繁的插入、删除操作，还会导致频繁的内存申请和释放，容易造成内存碎片，如果是 Java 语言，就有可能会导致频繁的 GC（Garbage Collection，垃圾回收）。

解答开篇

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

  1. 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
  2. 如果此数据没有在缓存链表中，又可以分为两种情况
    1. 如果此时缓存未满，则将此结点直接插入到链表的头部；
    2. 如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部

我们可以继续优化这个实现思路，比如引入散列表（Hash table）来记录每个数据的位置，将缓存访问的时间复杂度降到 O(1)。