# LRU cache design using dict and doubly linked list

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

• get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

• set(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.

This problem can be easily solved by using collections.OrderedDict. But I'd like to do the practice by using dict and doubly linked list. Can anyone help me check the following code?

class LRUCache:
# dictionary + doubly linked list
class Node:
def __init__(self, key, value):
self.prev = None
self.key = key
self.value = value
self.next = None

# @param capacity, an integer
def __init__(self, capacity):
self.capacity, self.dict = capacity, {}

# @return an integer
def get(self, key):
if key not in self.dict:
return -1
else:
return self.dict[key].value

# @param key, an integer
# @param value, an integer
# @return nothing
def set(self, key, value):
if key in self.dict:
self.dict[key].value = value
else:
if len(self.dict) >= self.capacity: # remove the least recently used element
self.dict[key] = self.Node(key, value)
self.insertNodeAtFirst(self.dict[key])

node.prev.next = node.next
node.next.prev = node.prev
node.prev = None
node.next = None
return node

def insertNodeAtFirst(self, node):


First off, the way you're commenting your functions is completely wrong. Proper commenting for functions uses Python docstrings. For example:

def my_func( ... ):
"""
Write a description of your
function and it's arguments
here.
"""
...


Secondly, according to Python's official style guide, PEP8, your naming is incorrect. Variables and functions should be in snake_case, and classes should be in PascalCase. If the variable is a constant, it should be in UPPERCASE_SNAKE_CASE.

Finally, why do you have Node as a subclass of LRUCache? Why can't Node be a top-level class? I see no reason it shouldn't be.