LRU算法
简述
LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。 该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中其t 值最大的，即最近最少使用的页面予以淘汰。
需求
实现一个缓存功能，使得插入、删除、修改的操作都是O(1)的，并且当需要清除缓存时，需要从最少使用的开始清除。
实现
思考：
- 一般的，要实现O(1)的时间复杂度，考虑使用hash来实现
- 需要从最少的元素开始删起，一种朴素的想法就是将每个元素使用时间记录下来，按时间顺序排好序，然后需要删除时，从最久未使用的元素开始删除
- 进而可以想到，使用链表将哈希表串联起来，头部表示使用最近使用的，尾部表示最久未使用的
如图所示：
最左边为Head，表示最近使用的；最右边未Tail，表示最久未使用的
当对节点进行操作：
删除：将节点从链表中移除
增加：将节点移动到head处
修改：将节点移动到head处
查询：将节点移动到head处