Sponsored
Sponsored
This approach combines a Doubly Linked List with a HashMap to maintain the LRU functionality. The doubly linked list keeps track of the order of elements. The head of the list represents the most recently used item, whereas the tail represents the least recently used item. Through a HashMap, we achieve O(1) access time complexity for updating and retrieving values. On cache misses that result in a new insertion when the cache is full, we evict the last node of the list.
Time Complexity: O(1) for both get and put operations due to the hashmap and linked list. Space Complexity: O(n), where n is the capacity of the cache for the hashmap and linked list.
1class Node:
2 def __init__(self, key, value):
3 self.key = key
4 self.value = value
5 self.prev = None
6 self.next = None
7
8class LRUCache:
9 def __init__(self, capacity: int):
10 self.capacity = capacity
11 self.cache = {}
12 self.head = Node(0, 0)
13 self.tail = Node(0, 0)
14 self.head.next = self.tail
15 self.tail.prev = self.head
16
17 def _remove(self, node):
18 prev = node.prev
19 next = node.next
20 prev.next, next.prev = next, prev
21
22 def _add(self, node):
23 n = self.head.next
24 self.head.next = node
25 node.prev = self.head
26 node.next = n
27 n.prev = node
28
29 def get(self, key: int) -> int:
30 if key in self.cache:
31 node = self.cache[key]
32 self._remove(node)
33 self._add(node)
34 return node.value
35 return -1
36
37 def put(self, key: int, value: int) -> None:
38 if key in self.cache:
39 self._remove(self.cache[key])
40 node = Node(key, value)
41 self._add(node)
42 self.cache[key] = node
43 if len(self.cache) > self.capacity:
44 lru = self.tail.prev
45 self._remove(lru)
46 del self.cache[lru.key]The Python solution defines a node class to handle key-value pairs and handles the LRU logic in the LRUCache class. The nodes are stored in a doubly linked list, allowing quick updates and removals. The cache (dictionary) maps keys to their nodes, providing O(1) time complexity for get and put operations.
This approach leverages built-in ordered dictionary data structures available in some languages. These structures inherently maintain the order of insertion, allowing for easy eviction of the least recently used item.
Time Complexity: O(1) for get and put since OrderedDict operations are optimized for simplicity and efficiency. Space Complexity: O(n), with n being the capacity of the cache.
1from collections import OrderedDict
2
3class LRUCache:
This Python solution uses the OrderedDict from the collections module. The inherent order tracking of OrderedDict facilitates moving accessed elements to the front or end of the dictionary easily, simplifying the logic for keeping track of least recently used items.