Break down LRU into helper methods:
function addToFront(node):
node.next = head.next
node.prev = head
head.next.prev = node
head.next = node
function removeNode(node):
node.prev.next = node.next
node.next.prev = node.prev
function moveToFront(node):
removeNode(node)
addToFront(node)
function 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.
Store the key in each node so you can remove from the hash map when evicting.