LRUCache for integers using dict + linkedlist

Question

From leet code question: https://leetcode.com/problems/lru-cache/

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?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

Code: Filename: lru_cache.py

#!/usr/bin/env python3
# -*- coding: utf-8 -*-


class Node:
    def __init__(self, key: int, val: int, prv=None, nxt=None):
        self.prv = prv
        self.nxt = nxt
        self.val = val
        self.key = key

    def __str__(self):
        nx = str(self.nxt)
        return "{}:{} -> {}".format(self.key, self.val, nx)


class LRUCache:
    def __init__(self, capacity: int):
        """
        :type capacity: int
        """
        self.first = None
        self.last = None
        self.cap = capacity
        self.cache = {}
        self.size = 0

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key not in self.cache:
            return -1

        node = self.cache[key]

        if self.first is self.last:
            return node.val

        if node is self.last:
            return node.val

        if node is self.first:
            nxt = node.nxt
            nxt.prv = None
            self.first = nxt
            node.nxt = None
        else:
            # In the middle
            nxt = node.nxt
            prv = node.prv
            node.nxt = None
            prv.nxt = nxt
            nxt.prv = prv

        self.last.nxt = node
        node.prv = self.last
        self.last = node
        return node.val

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: void
        """
        if self.get(key) != -1:
            # Already have
            self.cache[key].val = value
            return

        node = Node(key, value)

        if not self.first:
            self.size = 1
            self.first = node
            self.last = node
            self.cache[key] = node
            return

        self.cache[key] = node
        self.last.nxt = node
        node.prv = self.last
        self.last = node
        self.size = len(self.cache)

        if self.size > self.cap:
            # Need to remove
            first = self.first
            nxt = first.nxt
            nxt.prv = None
            self.first = nxt
            del self.cache[first.key]
            self.size = self.cap

    def __str__(self):
        return "LRUCache:: {}".format(self.first)


def _test():
    cache = LRUCache(2)

    cache.put(1, 1)
    cache.put(2, 2)
    assert cache.get(1) == 1  # returns 1
    cache.put(3, 3)  # evicts key 2
    assert str(cache) == "LRUCache:: 1:1 -> 3:3 -> None"
    assert cache.get(2) == -1  # returns -1 (not found)
    cache.put(4, 4)  # evicts key 1
    assert str(cache) == "LRUCache:: 3:3 -> 4:4 -> None"
    assert cache.get(1) == -1  # returns -1 (not found)
    assert cache.get(3) == 3  # returns 3
    assert cache.get(4) == 4  # returns 4
    assert str(cache) == "LRUCache:: 3:3 -> 4:4 -> None"


if __name__ == "__main__":
    _test()

What I want reviewed:

1. How pythonic the code is? How can I improve it.
2. Is there any area I can optimise performance ? (This passes all tests on leet-code)
3. Readability improvements?
4. Structure of the code file? Can we place things better?

You are welcome to be strict and brutal.

Additional info:

• I've used black to format code.

Answer 1

Use more abstract data types

In the current implementation two behaviors are mixed together:

• Caching
• Linked list manipulation

It would be better if the linked list manipulation was encapsulated in a dedicated abstract data type. Then LRUCache could use an instance of it, and perform operations that have nice descriptive names like append_node, delete_node, instead of blocks of nameless code. It will reveal more clearly the implemented logic of both the caching and linked list behaviors, and be more intuitively readable.

Avoid unclear side effects

At first glance I found this piece surprising in put:

if self.get(key) != -1:
    # Already have
    self.cache[key].val = value
    return

Why self.get(key) != -1 instead of key not in self.cache? The self.get is of course necessary, for its side effect of moving the node to the end. This may be subjective, but I would prefer to have an explicit private method that moves the node, and call it from both get and put. That will make the intention perfectly clear. Another reason I prefer that is to eliminate using the magic value -1 more than necessary.