I would like to ask for code review for my LRU Cache implementation from leetcode.
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
get(key)
- Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.put(key, value)
- Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.Follow up: Could you do both operations in O(1) time complexity?
I make sure that I used the LinkedListNode
class to make sure the solution is optimal with O(1) time complexity.
class ListNode(object):
def __init__(self, key, val):
self.val = val
self.key = key
self.next = None
self.prev = None
class LinkedList(object):
def __init__(self):
self.head = None
self.tail = None
def insert(self, node):
node.next, node.prev = None, None # avoid dirty node
if self.head is None:
self.head = node
else:
self.tail.next = node
node.prev = self.tail
self.tail = node
def delete(self, node):
if node.prev:
node.prev.next = node.next
else:
self.head = node.next
if node.next:
node.next.prev = node.prev
else:
self.tail = node.prev
node.next, node.prev = None, None # make node clean
class LRUCache(object):
# @param capacity, an integer
def __init__(self, capacity):
self.list = LinkedList()
self.dict = {}
self.capacity = capacity
def _insert(self, key, val):
node = ListNode(key, val)
self.list.insert(node)
self.dict[key] = node
# @return an integer
def get(self, key):
if key in self.dict:
val = self.dict[key].val
self.list.delete(self.dict[key])
self._insert(key, val)
return val
return -1
# @param key, an integer
# @param value, an integer
# @return nothing
def put(self, key, val):
if key in self.dict:
self.list.delete(self.dict[key])
elif len(self.dict) == self.capacity:
del self.dict[self.list.head.key]
self.list.delete(self.list.head)
self._insert(key, val)
This passes the leetcode tests.
get(key)
&put(key, value)
from the problem statement, where theLinkedListNode
class from the introduction - and the entire LRU cache, actually? \$\endgroup\$