lru-cache.py

"""
In this python implementation of LRUCache,
We are using a hashmap `cache={}` to be able to retrieve data at O(1) and
using a Doubly Linked List to maintain the order of keys to know which one
are most recently used to least recently used as we move from head to tail.
"""


class Node:
   def __init__(self, key, value, next=None, prev=None) -> None:
       self.key = key
       self.value = value
       self.next = next
       self.prev = prev


class LRUCache:
   def __init__(self, size=100) -> None:
       self.size = size
       self.cache = {}
       self.head = Node(0, 0)         # most recently used towards the head
       self.tail = Node(0, 0)         # least recently used towards the tail
       self.head.next = self.tail
       self.tail.prev = self.head


   def add_link(self, node: Node):
       """
       It adds a given node to the linked list at the beginning next to the head of the DDL. This
       function helps maintaining the order of nodes in the doubly-linked-list which keeps
       track of most recently used to least recently used nodes from head to tail.
       """
       # add pointers to place the new node right after the head
       node.prev = self.head
       node.next = self.head.next


       # update pointers for head and next neighbor of new node for it's placement
       self.head.next.prev = node
       self.head.next = node


   def remove_link(self, node: Node):
       """
       It removes a given node from the doubly linked list by assigning it's next & previous
       pointers to its next & previous neighbors and removing itself from the links. This
       function helps maintain the order of nodes in the doubly-linked-list.
       """
       node.prev.next = node.next
       node.next.prev = node.prev
     
   def get(self, key: int):
       """
       Returns the value for the given key from the cache and updates the pointers to indicate
       most recently used cache item.
       """
       if key in self.cache:
           # if the key already exists in cache, we simply return the value and update it position
           # to indicate it's most recently used key by placing it next to the head
           self.remove_link(self.cache[key])
           self.add_link(self.cache[key])
           return self.cache[key].value
       return None


   def put(self, key:int, value: int):
       """
       Adds the key, value pair to cache while maintaining the size of the cache.
       """
       if key in self.cache:
           # check if it already exists in cache, then we simply remove it from it's existing
           # place and add a new node with updated value next to the head indicating most recent
           self.remove_link(self.cache[key])
       self.cache[key] = Node(key, value)
       self.add_link(self.cache[key])
     
       # check if the cache is exceeding set size limit, purge the last used item from cache
       # which is available just before (previous to) the tail
       if len(self.cache) > self.size:
           lru_node = self.tail.prev
           self.remove_link(lru_node)
           del self.cache[lru_node.key]