LeetCode 146. LRU Cache

Dict and LinkedList

If we did not have to evict keys, we could just keep a {key -> value} map.

When there are too many keys, we need to evict the least-recently-used key therefore the key for which a get or put was called furthest into the past. As a result, we need to also maintain time-order among (key, value) pairs. To maintain time-order, we use a linked list. A key move to the head of the linked list if a get or put is called on the key. So, the head is the most-recently-used key and the tail is the least-recently-used key. On get or put, we just need to keep the dict and LinkedList in sync.

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

class LinkedList:
    def __init__(self):
        self.head, self.tail = None, None
    
    def append_to_head(self, node):
        if not self.head:
            self.head = node
            self.tail = node
            return
        
        node.next = self.head
        self.head.prev = node
        self.head = node

    def __remove_node(self, node):
        prev_node = node.prev
        if not prev_node:
            # node is head
            self.head = node.next
            if not self.head:
                self.tail = None

            node.prev, node.next = None, None
            return node
        
        next_node = node.next
        if not next_node:
            # node is tail
            prev_node.next = None
            self.tail = prev_node

            node.prev, node.next = None, None
            return node

        prev_node.next = next_node
        next_node.prev = prev_node

        node.prev, node.next = None, None
        return node

    def move_to_head(self, node):
        if node == self.head:
            return
        
        removed_node = self.__remove_node(node)
        self.append_to_head(removed_node)

    def remove_from_tail(self):
        removed_node = self.__remove_node(self.tail)
        return removed_node

class LRUCache:

    def __init__(self, capacity: int):
        self.cap = capacity
        self.key_node_map = {}
        self.linked_list = LinkedList()

    def get(self, key: int) -> int:
        if key not in self.key_node_map:
            return -1
        
        node = self.key_node_map[key]
        self.linked_list.move_to_head(node)

        return node.value

    def put(self, key: int, value: int) -> None:
        if key in self.key_node_map:
            node = self.key_node_map[key]
            node.value = value
            self.linked_list.move_to_head(node)
        else:
            node = ListNode(key, value)
            self.key_node_map[key] = node
            self.linked_list.append_to_head(node)
        
        if len(self.key_node_map) > self.cap:
            node = self.linked_list.remove_from_tail()
            del self.key_node_map[node.key]


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

Operation	Time	Space
`__init__`	$\mathcal{O}(1)$	$\mathcal{O}(1)$
`get`	$\mathcal{O}(1)$	$\mathcal{O}(1)$
`put`	$\mathcal{O}(1)$	$\mathcal{O}(1)$

unreasonably effective