LRU, Least Recently Used 近期最少使用算法, 常应用于缓存中的数据淘汰。也就是说最近最多使用的元素，出现的几率还是很高的，应该保持这种元素持续存在缓存中。
那么，应该使用什么数据结构才能满足要求呢？如下图：
92033a96-da60-11e4-8754-66135bb0d233.png
这不是双向链表么？表头代表最近使用过的数据，表尾表示最久没有使用过的数据。当需要删除旧数据时，可以通过删除表尾节点，然后在表头接入一个新节点。而更新节点时，可以把原来的节点删除掉，然后重新接入表头。如果插入时没有达到容量的上限的话，可以一直往表头插入节点。
实现中有一点需要注意，由于链表查找数据，需要从表头一步步查询到表尾，查找速度比较慢，
所以我们可以使用Python的字典类型来存储数据的键值对。查找时，先判断是否存在于字典中，
如果在，需要更新节点的使用情况并返回结果，没有就返回-1。
实现
class LRUCache(object):
class Node(object):
def __init__(self, key, value):
self.key = key
self.value = value
self.prev = None
self.next = None
def __init__(self, capacity):
self.capacity = capacity
self.size = 0
self.items = {} # 存节点的键值对，方便查找某节点是否存在链表中
self.head = self.Node(-1, -1) # 双向链表头初始化
self.tail = self.Node(-1, -1) # 双向链表尾初始化
self.head.next = self.tail # 将头与尾连接起来
self.tail.prev = self.head
def __remove(self, node):
"""remove node.
:params node: remove this node
"""
node.prev.next = node.next # 当前节点的前节点的next指向当前节点的后节点
node.next.prev = node.prev # 当前节点的后节点的prev指向当前节点的前节点
node.prev = None #把当前节点的前节点置空
node.next = None
def __insert(self, node):
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def get(self, key):
if key not in self.items:
return -1
node = self.items[key]
self.__remove(node) # 先删除该节点，然后在表头重新接入
self.__insert(node)
return node.value
def put(self, key, value):
if key in self.items:
node = self.items[key]
self.__remove(node)
node.value = value
self.__insert(node)
else:
# 判断LRU缓存中是否已经达到最大容量，是的话就删除表尾节点，然后再执行插入操作
if self.size == self.capacity:
discard = self.tail.prev
self.__remove(discard)
del self.items[discard.key]
self.size -= 1
node = self.Node(key, value)
self.items[key] = node
self.__insert(node)
self.size += 1
