LRU Helper Methods

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.