LRU Cache

2 min read
LC-Medium
Linked List

Oct 21, 2022

3 years ago

LeetCode

Solution

Use a Doubly Linked List
With an array, this solution is very easy to implement but the time complexity would be O(n), and the question asks for O(1)
Have dummy head and tail pointers.
Whenever inserting a new node, insert it right after head.
This way, the least recently used node is the node before tail.
Whenever you get a key, we need to move it to the most recently used (i.e. near head), so you can either delete and insert after head, or change the node's pointers (and also the pointers of it's prev and next)
Also remember that whenever evicting a key, remove it from your hashmap as well.
DO NOT WATCH NEETCODE'S VIDEO. WATCH THIS INSTEAD: https://www.youtube.com/watch?v=xDEuM5qa0zg
Also remember, you won't understand much if you just look at the code I've written. Look at the video above for better results

Time	Space	Explanation
`O(1)`	`O(?)`

class Node: def __init__(self, key, val): self.key, self.val = key, val self.prev, self.next = None, None class LRUCache: def __init__(self, capacity: int): self.size = 0 self.capacity = capacity self.nodes = {} # key: Node(value) self.head, self.tail = Node(0, 0), Node(0, 0) self.head.next = self.tail self.tail.prev = self.head def insert(self, key, val): node = Node(key, val) if self.size == self.capacity: # If capacity is reached, remove LRU node, which the node before tail self.remove(self.tail.prev.key) self.nodes[key] = node self.head.next.prev = node node.next = self.head.next node.prev = self.head self.head.next = node self.size += 1 def remove(self, key): node = self.nodes[key] node.prev.next = node.next node.next.prev = node.prev del self.nodes[key] self.size -= 1 return node def get(self, key: int) -> int: if key not in self.nodes: return -1 removed_node = self.remove(key) self.insert(key, removed_node.val) return removed_node.val def put(self, key: int, value: int) -> None: if key in self.nodes: self.remove(key) self.insert(key, value)