A LRU implementation using the above double linked list and a hashmap

lru_cache.py

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.key2node = {}
        self.nodelist = NodeList()
    
    def get(self, key):
        if key not in self.key2node:
            return -1
        node = self.key2node[key]
        self.nodelist.remove(node)
        self.nodelist.insert(node)
        return node.value
    
    def put(self, key, value):
        if key in self.key2node:
            old_node = self.key2node[key]
            self.nodelist.remove(old_node)
        
        new_node = Node(key, value)
        self.key2node[key] = new_node
        self.nodelist.insert(new_node)

        # evict the least used item if cache is over capacity
        if self.nodelist.size > self.capacity:
            least_used = self.nodelist.tail
            self.key2node.pop(least_used.key)
            self.nodelist.remove(least_used)