LRU Cache in constant time

Question

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.

• greybeard: Where is get(key) & put(key, value) from the problem statement, where the LinkedListNode class from the introduction - and the entire LRU cache, actually?

Answer 1

Usual comment: add """docstrings""" to public methods at the very least.

Avoid double (and triple) lookups. Python has fast exception handling. Instead of testing for existence, and then fetching the value, just fetch the value. And don’t fetch it more than once. Ie, replace this:

if key in self.dict:
 val = self.dict[key].val
 self.list.delete(self.dict[key])
 self._insert(key, val)
 return val 
else:
 return -1

with this:

try:
 node = self.dict[key]
 val = node.val
 self.list.delete(node)
 self._insert(key, val)
 return val 
except KeyError:
 return -1

Above, you are deleting/discarding a ListNode containing a key-value pair, and then immediately creating a new ListNode with the same key-value pair to insert. LinkedList.insert() takes the trouble to clean the node for insertion; why not reuse the node? You wouldn’t have to update self.dict[key], either.

Similar optimizations for put(): don’t do double lookups and possibly reuse node (but with updated .val).

Answer 2

Outside of beginners' programming courses and interview quizzes, linked lists are rarely useful. Theoretically, they may be efficient, but in practice, the memory allocation and memory fragmentation just isn't worth it. That may be why Python, which is supposed to come with "batteries included", does not come with a linked list in its standard library.

For a fixed-size queue, where the oldest entry is to be automatically discarded, a better data structure would be a circular-buffer, which in Python is provided by the collections.deque class. You should make a deque(maxlen=capacity) instead of your LinkedList.

• AJNeufeld: If this is not an exercise to create an LRU Cache from scratch, an OrderedDict could be an even better data structure. It is a dictionary and ordered list in one. It has built in methods .move_to_end(key) which would mark the entry most recently used, and .popitem() which will remove the oldest entry.