链表

常见淘汰策略

• FIFO（First In，First Out）先进先出；
• FILO 先进后出；
• LFU（Least Frequently Used）最少使用；
• LRU（Least Recently Used）最近最少使用。

链表的特性

不需要连续的储存空间，而是通过指针讲一堆零散的内存快串联起来。；

单链表

• 后继指针：由于数据存储不连续，所以链表中的每一个节点都需要记录下一个节点的地址，叫做后继指针；
• 头节点，记录了链表的基地址；
• 尾节点，后继指针指向空地址null。

由于数组需要连续的储存空间，所以在增删操作时需要移位补漏，所以时间复杂度是O(n)，而链表因为空间本身不是连续的，所以不需要移位，所以时间复杂度是O(1)。

循环链表

• 一种特殊的单项链，尾节点的后继指针指向头节点。
• 从链尾可以轻松返回链头。
• 当数据具备环形特点时适合使用循环链表。

双向链表

节点中同时具备前驱和**后继双指针

LRU算法

在一个固定长度并且有序的链表结构中存入数据，由于有序，所以最先插入的就会排在链尾。

当访问数据时，从链头开始遍历查询到对应节点，并将它移到链头；

如果没有查询到，则将新数据插入链头。

如果插入后发现链表已超出固定长度，则删除链尾。