Core Insight Before changing a link, save the only pointer that would otherwise be lost.
Common Pitfall Always store next before redirecting current.next.
Description
Design and implement a data structure for Least Recently Used cache.
Constraints
- Time Complexity:
O(1) - Space Complexity:
O(n)
Tags
hash-maplinked-listdesigndoubly-linked-list
Implementation Plan Translate the invariant into these small, testable moves.
- Initialize the pointers.
- Save the next node.
- Rewire the current node.
- Advance both pointers until the list is consumed.
class Node:
def __init__(self, key, val):
self.key, self.val = key, val
self.prev = self.next = None
class LRUCache:
def __init__(self, capacity):
self.cap = capacity
self.cache = {}
self.left, self.right = Node(0, 0), Node(0, 0)
self.left.next, self.right.prev = self.right, self.left
def remove(self, node):
prev, nxt = node.prev, node.next
prev.next, nxt.prev = nxt, prev
def insert(self, node):
prev, nxt = self.right.prev, self.right
prev.next = nxt.prev = node
node.prev, node.next = prev, nxt
def get(self, key):
if key in self.cache:
self.remove(self.cache[key])
self.insert(self.cache[key])
return self.cache[key].val
return -1
def put(self, key, value):
if key in self.cache:
self.remove(self.cache[key])
self.cache[key] = Node(key, value)
self.insert(self.cache[key])
if len(self.cache) > self.cap:
lru = self.left.next
self.remove(lru)
del self.cache[lru.key]