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.
1class LRUCache {
2 constructor(capacity)
This JavaScript solution utilizes the Map object. Map maintains the order of entries, enabling the quick updating and eviction needed for the LRU cache. Each get operation involves removing and reinserting the accessed element to retain ordering.