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.