Break down LRU into helper methods:
def addToFront(node):
node.next = head.next
node.prev = head
head.next.prev = node
head.next = node
def removeNode(node):
node.prev.next = node.next
node.next.prev = node.prev
def moveToFront(node):
removeNode(node)
addToFront(node)
def removeLRU():
lru = tail.prev
removeNode(lru)
return lru.key # need key to remove from map
The dummy head and tail ensure addToFront and removeNode never deal with null pointers. This simplifies the code significantly.
Store the key in each node so you can remove from the hash map when evicting.