# LRUCache for integers using dict + linkedlist

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.put(4, 4);    // evicts key 1
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:
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"
cache.put(4, 4)  # evicts key 1
assert str(cache) == "LRUCache:: 3:3 -> 4:4 -> None"
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)
4. Structure of the code file? Can we place things better?

You are welcome to be strict and brutal.

• I've used black to format code.

### Use more abstract data types

In the current implementation two behaviors are mixed together:

• Caching

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:

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.