为实现最近最少使用算法(LRU),我们做以下假定:
数据结构: 单个节点:存在左指针,右指针,KEY,VALUE 缓存表:存在头节点,尾节点,链表长度,MAP MAP:键和对应的值
基本操作: 新建LRU缓存: 新建一个上述提到的MAP和缓存表结构,初始化左节点和尾节点
GET: 在MAP里进行查找,如果不存在对应的缓存,则返回空/错误 如果存在,则根据MAP找到对应的节点位置,根据链表操作,将其移动至头节点,并返回值
PUT: 首先进行MAP,如果有值,则根据其位置修改值 如果没有,首先检测是否链表长度满,如果满,则删除MAP里尾指针的索引,并删除尾节点 之后,将该指针新建至头部