# 146. LRU Cache LRU 缓存

@TOC

## # 题目描述

Design and implement a data structure for `Least Recently Used (LRU)` cache. It should support the following operations: `get` and `put`.

• `get(key)` - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
• `put(key, value)` - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a `positive` capacity.

Follow up: Could you do both operations in `O(1)` time complexity?

Example:

``````LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.put(4, 4);    // evicts key 1
cache.get(3);       // returns 3
cache.get(4);       // returns 4
``````

## # 题目大意

LRU算法的设计原则是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。

## # 解题方法

### # 字典+双向链表

1. 把一个节点从链表中删除（这就是为什么选择双向链表的原因，方便找到前后节点）
2. 把一个节点放入链表的头部（需要一个不保存数据的root节点，其prev和next分别指向链表尾部和头部）

python代码如下：

``````class ListNode:
def __init__(self, key, value):
self.key = key
self.value = value
self.prev = self
self.next = self

class LRUCache:

def __init__(self, capacity: int):
self.dic = dict()
self.capacity = capacity
self.size = 0
self.root = ListNode(0, 0)

def get(self, key: int) -> int:
if key in self.dic:
node = self.dic[key]
self.removeFromList(node)
return node.value
else:
return -1

def put(self, key: int, value: int) -> None:
if key in self.dic:
node = self.dic[key]
self.removeFromList(node)
node.value = value
else:
if self.size >= self.capacity:
self.removeFromTail()
self.size -= 1
node = ListNode(key, value)
self.dic[key] = node
self.size += 1

def removeFromList(self, node):
if node == self.root: return
prev_node = node.prev
next_node = node.next
prev_node.next = next_node
next_node.prev = prev_node
node.prev = node.next = None

node.prev = self.root
self.root.next = node

def removeFromTail(self):
if self.size == 0: return
tail_node = self.root.prev
del self.dic[tail_node.key]
self.removeFromList(tail_node)

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
``````

## # 日期

2019 年 9 月 13 日 —— 今天是中秋节，祝大家中秋快乐