缓存是开发中常用的一种技术.缓存的大小有限,当被用满时,就需要缓存淘汰策略来决定.
常见的三种策略:

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

常见的三种链表结构:

单链表:

链表通过指针将一组零散的内存串联在一起.其中,我们把内存块称为链表的”结点”.为了将所有结点串起来,每个链表的结点出了存储数据之外,还需要记录链上的下一个结点的地址.我们把下个结点地址的指针叫做后继指针next.

image.png

我们把第一个结点叫作头结点,最后一个结点叫:尾结点.其中,头结点用来记录链表的基地址(供我们遍历整条链表).尾结点特殊的地方是:指针不是指向下一个结点,而是指向一个空地址null,表示这是链表上最后一个结点.
单链表的插入和删除操作,时间复杂度为:链表:如何实现LRU缓存淘汰算法? - 图3,链表想要随机访问第K个元素时,时间复杂度为:链表:如何实现LRU缓存淘汰算法? - 图4.

循环链表:

循环链表是一种特殊的单链表.区别是:在尾结点的指针指向链表的头结点.
image.png

双向链表:

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