# LRU Cache in constant time

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.

## 2 Answers

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).

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 , which in Python is provided by the collections.deque class. You should make a deque(maxlen=capacity) instead of your LinkedList.

• 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. – AJNeufeld Aug 23 '18 at 15:41