LRU Cache implementation using a dictionary and Doubly linked list in Python

A cache is a temporary storage area that stores frequently accessed data so that it can be quickly retrieved when needed. One type of cache is an LRU (Least Recently Used) cache, which is designed to remove the least recently used items when the cache becomes full. Read more about LRU here.

An LRU cache can be implemented using a dictionary to store the cache data, and a doubly linked list to represent the order of the cache items. Here, the dictionary is used to map keys to nodes in the linked list, and the linked list is used to represent the order of the items, with the head node representing the least recently used item, and the tail node representing the most recently used item.

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

class LRUCache:

    def __init__(self, capacity: int):
        self.map = dict()
        self.capacity = capacity
        self.head = ListNode(0, 0)
        self.tail = ListNode(-1, -1)
        self.head.next = self.tail
        self.tail.prev = self.head


    def get(self, key: int) -> int:
        if key in self.map:
            node  = self.map[key]
            self._removeFromList(node)
            self._insertIntoHead(node)
            return node.value 
        else:
            return -1 


    def set(self, key: int, value: int) -> None:
        if key in self.map:
            node = self.map[key]
            self.removeFromList(node)
            self.insertIntoHead(node)
            node.value = value 
        else:
            if len(self.map) >= self.capacity:
                self._removeFromTail()
            node = ListNode(key,value)
            self.map[key] = node
            self._insertIntoHead(node)

    def _removeFromList(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _insertIntoHead(self, node):
        headNext = self.head.next 
        self.head.next = node 
        node.prev = self.head 
        node.next = headNext 
        headNext.prev = node

    def _removeFromTail(self):
        if len(self.map) == 0: return
        tail_node = self.tail.prev
        del self.map[tail_node.key]
        self._removeFromList(tail_node)


# cache = LRUCache(capacity)
# cache.get(key)
# cache.set(key, value)

Your engagements are welcome. Subscribe for more such low-level design questions frequently asked in tech interviews