Why Use an LCU Cache ?#

LRU is built on the principle of Temporal Locality. If a piece of data was accessed recently, it is highly likely to be accessed again soom.

LRU keeps this “hot” data ready for instant access.

Discussion#

To achieve get and put in O(1) time complexity, an LRU cache is implemented using two data structures :

• Doubly Linked List :

  • Most Recently Used (MRU) : keep at the head

  • Least Recently Used (LRU): keep at the tail

    A doubly linked list allows us to disconnect a node in O(1) because we have pointers to both its prev and next.

• Hash Map : enables O(1) node lookup.

When we think about how get and put design,

• get

  1. Check the hash map. If the key doesn’t exist, return -1.
  2. If it exists, use the pointer retrieved from hash map, remove it from its current position and insert it at the head.

• put

  1. If the key already exists, update the value and move it to the head.
  2. If it’s a new key, insert it at the head and add new entry to hash map. If capacity if full, remove the node at the tail.

Solution#

class Node:
    def __init__(self, key: int, val: int):
        self.key, self.val = key, val
        self.prev = self.next = None

class LRUCache:

    def __init__(self, capacity: int):
        self.cap = capacity
        self.dict = {} # hash table, look up for node
        self.head, self.tail = Node(0,0), Node(0,0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def _add_to_head(self, node: Node):
        self.head.next.prev = node
        node.next = self.head.next
        self.head.next = node
        node.prev = self.head

    def _remove(self, node: Node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def get(self, key: int) -> int:
        if key not in self.dict:
            return -1
        # get node + add to head (update priority, recent used)
        node = self.dict[key]
        self._remove(node)
        self._add_to_head(node)
        return node.val


    def put(self, key: int, value: int) -> None:
        # if exists (update): remove old node + add to head
        # if not (new): add to head + remove least used node if
        # exceed capacity

        if key in self.dict:
            old_node = self.dict[key]
            self._remove(old_node)

        node = Node(key, value)
        self.dict[key] = node
        self._add_to_head(node)

        if len(self.dict) > self.cap:
            del_node = self.tail.prev
            self._remove(del_node)
            del self.dict[del_node.key]