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.

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.