Link to problem: https://leetcode.com/problems/lru-cache/

LRU is a very common cache eviction policy. If we only query each key once (and it’s no longer queried until it is evicted), then the LRU cache is basically a fixed-size FIFO queue, and we can implement that with a circular array or a linked list. Because we do want to move a node to the front of the queue when a key is queried while in cache, we can be certain that we want to use a linked list. Here we choose to use a doubly linked list, because we can delete a node in a doubly linked list with only reference to that node, while in a singly linked list we would need the reference to the previous node as well.

In a linked list, moving a given node to the front only requires $\O(1)$ time, but it takes $\O(n)$ time to find that node with sequential search. In order to realize $\O(1)$ put and get, we need the help from a hash table. We use a dictionary to map keys to their corresponding list nodes, so we can find the node to move in $\O(1)$ time.

Another useful trick is to use two dummy nodes as the head and tail nodes. With them, we can treat the actual head and tail in the same way as other nodes in the middle.

LRU 缓存是非常常用的缓存驱逐策略。如果每个 key 只被使用一次（直到它被驱逐之前不会再被 get 或者 put），那 LRU 缓存就相当于一个固定容量的 FIFO 队列，我们可以想到使用循环数组或者链表来实现。但是每个 key 可能在还在缓存中的时候就被再次使用，因此我们需要把队列中的某一项移到队列头部，所以我们可以确定应该选择使用链表。这里我们采用双向链表，因为在双向链表中移除一个结点只需要该结点的引用就可以实现，而在单向链表中还需要获得其前序结点的引用。

class DLinkedNode:
def __init__(self, key, value):
self.key = key
self.value = value
self.left = None
self.right = None

class LRUCache:

def __init__(self, capacity: int):
self.capacity = capacity
self.cache = dict()  # key -> DLinkedNode
self.head = DLinkedNode(0, 0)
self.tail = DLinkedNode(0, 0)
self.head.right = self.tail
self.tail.left = self.head

def _printLinkedList(self):
curr = self.head
r = ""
while curr:
if curr == self.head:
r += "HEAD"
elif curr == self.tail:
r += "TAIL"
else:
r += "({}, {})".format(curr.key, curr.value)
curr = curr.right
print(r)

def get(self, key: int) -> int:
if key in self.cache:
node = self.cache[key]
self._deleteNode(node)
self._addNode(node)
# self._printLinkedList()
return node.value
else:
return -1

def put(self, key: int, value: int) -> None:
if key in self.cache:
self._deleteNode(self.cache[key])
newNode = DLinkedNode(key, value)
self._addNode(newNode)
self.cache[key] = newNode
if len(self.cache) > self.capacity:
toDelete = self.tail.left
self._deleteNode(toDelete)
del self.cache[toDelete.key]
# self._printLinkedList()

def _deleteNode(self, node):
node.left.right = node.right
node.right.left = node.left

def _addNode(self, node):
oldFirst = self.head.right
oldFirst.left = node
node.right = oldFirst
node.left = self.head
self.head.right = node

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