Python solution with implementing Deque

• ``````class _Node:
def __init__(self, key, value):
self.key = key
self.value = value
self.pre = None
self.next = None

class _Deque:
def __init__(self):
self.size = 0

def __len__(self):
return self.size

def pop(self):
node = self.tail
self.tail = self.tail.pre
self.tail.next = None
self.size -= 1
return node

def appendleft(self, node):
else:
self.tail = node
self.size += 1

def remove(self, node):
if not node.next:  # node is tail
self.tail = self.tail.pre
self.tail.next = None
else:
node.next.pre = node.pre
node.pre.next = node.next
self.size -= 1

class LRUCache:
# @param capacity, an integer
def __init__(self, capacity):
self.capacity = capacity
self.dq = _Deque()
self.k2v = {}

# @return an integer
def get(self, key):
if key not in self.k2v:
return -1
node = self.k2v[key]
self.dq.remove(node)
self.dq.appendleft(node)
return node.value

# @param key, an integer
# @param value, an integer
# @return nothing
def set(self, key, value):
if key not in self.k2v:
if len(self.dq) == self.capacity:
old_node = self.dq.pop()
del self.k2v[old_node.key]
node = _Node(key, value)
self.dq.appendleft(node)
self.k2v[key] = node

else:
node = self.k2v[key]
self.dq.remove(node)
self.dq.appendleft(node)
node.value = value
``````

If we use `collections.deque.remove()`, it's O(n). As a result, I implement a simple Deque.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.