基于单链表的LRU缓存淘汰机制

单链表实现LRU缓存淘汰算法

什么是LRU缓存淘汰算法

由于计算机内存中缓存容量存在限制，当缓存空间被填满后，必须借助特定算法将部分缓存内容进行置换。目前较为常见的算法包括FIFO（先进先出）、LFU（最少使用）以及LRU（最近最少使用）等。

LRU（Least Recently Used）算法通常被称为最近最少使用算法。从名称可以推测，当缓存已满且需引入新数据时，系统倾向于保留近期被访问过的数据块，因为这些数据再次被调用的可能性较高。因此，在这种情况下，应优先淘汰在最近一段时间内使用频率最低的数据块。

思路

构建一个单链表结构，用于模拟内存中的缓存管理机制，其中链表的末尾节点代表最近最少被访问的缓存项。当系统需要访问某块数据时，需根据以下三种情形进行处理：

1. 若所访问的数据已存在于缓存中，则需将对应的缓存节点调整至链表的起始位置；
2. 若所访问的数据不在缓存中，且当前缓存仍有可用空间，则将该数据作为新节点插入至链表的头部；
3. 若所访问的数据不在缓存中，而当前缓存已达到容量上限，则应移除链表末尾的缓存节点，并将新数据插入至链表头部。

代码实现

    #include <iostream>
    
    using namespace std;
    
    typedef int Dat