LRU cache design using dict and doubly linked list

Question

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, {}
 self.head, self.tail = self.Node('head', 'head'), self.Node('tail', 'tail') # dummy head node and dummy tail node
 self.head.next = self.tail
 self.tail.prev = self.head
 # @return an integer
 def get(self, key):
 if key not in self.dict:
 return -1
 else:
 self.insertNodeAtFirst(self.unlinkNode(self.dict[key]))
 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.insertNodeAtFirst(self.unlinkNode(self.dict[key]))
 self.dict[key].value = value
 else:
 if len(self.dict) >= self.capacity: # remove the least recently used element
 del self.dict[self.unlinkNode(self.tail.prev).key]
 self.dict[key] = self.Node(key, value)
 self.insertNodeAtFirst(self.dict[key])
 def unlinkNode(self, node):
 node.prev.next = node.next
 node.next.prev = node.prev
 node.prev = None
 node.next = None
 return node
 def insertNodeAtFirst(self, node):
 node.prev = self.head
 node.next = self.head.next
 self.head.next.prev = node
 self.head.next = node

Answer 1

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.