LC 146

Solution to LeetCode 146 LRU Cache.

LeetCode 146

LRU Cache (Medium). [link]

The problem requires functions get and put must each run in O(1) average time complexity. We use HashTable + Doubly directed linked list. The HashTable is used to store the key and value of a node so that we can find the node easily. The doubly directed linked list makes it easy to add and remove nodes. So the time complexity of put and get is O(1), the space complexity is O(capacity).

Using Double Linked List to mimic a cache so it’s easy to add and remove carrying value and key, and using a HashTable to locate the keys on the linked list so it is easy to find any key in O(1) time.

Double linked list is better than a single linked list: if we want to remove the node in the tail, we can directly find it in a double linked list. However, we need to traverse through a single linked list in order to get the tail node.

class DoublyLinkedNode:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.cache = dict()
        self.head = DoublyLinkedNode()
        self.tail = DoublyLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.capacity = capacity
        self.size = 0

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key not in self.cache: # not found
            return -1
        node = self.cache[key]
        self.moveToHead(node) # change the order
        return node.value

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None
        """
        if key not in self.cache: # if not found
            node = DoublyLinkedNode(key, value) # create one
            self.cache[key] = node # add key and value to the cache
            self.addToHead(node) # add node to the head of list
            self.size += 1
            if self.size > self.capacity:
                removed = self.removeTail() # remove node from the right of list
                self.cache.pop(removed.key) # remove the key from cache
                self.size -= 1
        else: # if key in cache
            node = self.cache[key]
            node.value = value # update the value
            self.moveToHead(node) # change the order 
    
    def addToHead(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
        
    def removeNode(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        
    def moveToHead(self, node):
        self.removeNode(node)
        self.addToHead(node)
    
    def removeTail(self):
        node = self.tail.prev
        self.removeNode(node)
        return node