mimic the internal implementation of OrderedDict

class LRUCache(object):
def __init__(self, capacity):
"""
:type capacity: int
"""
self.capacity = capacity
# https://github.com/python/cpython/blob/2.7/Lib/collections.py
# Node: [prev, next, key, val]
root = self._root = []
root[:] = [root, root, None, None]
self._data = {} # key -> node
def _pop(self, key=None):
root, data = self._root, self._data
if key is None:
node = root[1]
key = node[2]
else:
node = data[key]
prev, next, key, val = node
prev[1], next[0] = next, prev
del data[key]
return val
def _insert(self, key, val):
root, data = self._root, self._data
assert key not in data
prev = root[0]
node = [prev, root, key, val]
prev[1] = root[0] = node
data[key] = node
def get(self, key):
data, root = self._data, self._root
if not key in data: return -1
val = self._pop(key)
self._insert(key, val)
return val
def put(self, key, value):
data = self._data
if key in data:
self._pop(key)
if len(data) == self.capacity:
self._pop()
self._insert(key, value)