LRU缓存机制

实现LRU缓存机制,需要用到一个哈希表和一个双向链表。

两者的作用:

  • 哈希表:记录此数据结构(即上面提到的LRU缓存机制数据结构)中存在的键值对
  • 双向链表:双向链表按照被使用的顺序存储了这些键值对,靠近头部的键值对是最近使用的,而靠近尾部的键值对是最久未使用的。

当时看到这里有一个疑问,那就是为什么要用双向链表,不能用单向链表?

首先要知道一点:我们要始终保存head节点和tail节点的值,这样每次操作只需要吧tail移到head的前面即可。这个时候问题就出来了。如果使用单向链表,当我们把tail节点移动到head前时,我们当然可以令tail的next为head值,令head值为tail;但是此时新的tail(也就是旧的tail的前一个节点)值我们不能得到,想要得到就只能从头遍历一遍,因此要用双向链表。