This program implements a Least Recently Used (LRU) cache using Python. The LRU cache is designed to hold a specific number of items and evicts the least recently used item when new items need to be added and the cache is full.

Program Structure

The LRU cache is implemented using a combination of a dictionary and a doubly linked list. This allows O(1) time complexity for adding, removing, and accessing elements. The components are:

• A dictionary (hashmap) that points to nodes in a doubly linked list.
• Each node in the list represents an item in the cache with keys and values.
• The head of the list represents the most recently used item, while the tail represents the least recently used item.

Python Code

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

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.dict = {}
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def _add(self, node):
        p = self.head.next
        self.head.next = node
        node.prev = self.head
        node.next = p
        p.prev = node

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

    def get(self, key):
        if key in self.dict:
            node = self.dict[key]
            self._remove(node)
            self._add(node)
            return node.val
        return -1

    def put(self, key, value):
        if key in self.dict:
            self._remove(self.dict[key])
        node = Node(key, value)
        self.dict[key] = node
        self._add(node)
        if len(self.dict) > self.capacity:
            node = self.tail.prev
            self._remove(node)
            del self.dict[node.key]

# Example Usage
cache = LRUCache(3)
cache.put(1, 1)
cache.put(2, 2)
cache.put(3, 3)
print(cache.get(1))       # returns 1
cache.put(4, 4)           # evicts key 2
print(cache.get(2))       # returns -1 (not found)
print(cache.get(3))       # returns 3
print(cache.get(4))       # returns 4

Explanation of the Code

• Node class: Represents an item in the cache with key-value pairs and pointers to the next and previous nodes.
• LRUCache class: Manages the cache with methods to add, remove, and get items efficiently.
• _add and _remove methods: Helper methods to add and remove nodes from the doubly linked list, maintaining order based on usage.
• get and put methods: Provide external interfaces to access and add items to the cache, with automatic handling of eviction of the least recently used items.

Usage

The LRU cache can be used in scenarios where it’s important to maintain quick access to the most recently used data, such as in web servers for caching web pages or in applications for caching user-specific data.