0
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Where is get(key) & put(key, value) from the problem statement, where the LinkedListNode class from the introduction - and the entire LRU cache, actually? \$\endgroup\$
    – greybeard
    Apr 25, 2022 at 11:14

2 Answers 2

4
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$
    – AJNeufeld
    Aug 23, 2018 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.