LRU Cache

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

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.

class Node:
    def __init__(self, val=0, keyRef=0):
        self.keyRef = keyRef
        self.val = val
        self.next = None
        self.prev = None

class LRUCache(object):

    def __init__(self, capacity):
        """                             
        :type capacity: int                             
        """
        self.dict = {}
        self.head = Node() # head is a blank node                              
        self.tail = self.head # remove from the tail side, for FIFO implementation                              
        self.capacity = capacity
    '''                        
    1. If key not found in cache return -1                             
    2. If key found in cache, then return that val, remove the item from the current position and make it the newest element
    '''
    def get(self, key):
        """
        :rtype: int                             
        """
        if str(key) not in self.dict:
            return -1

        # Now, take the node from it's exisiting old position and make it current (make it the first node after head)
        # Also, return the node value
        nodeRef = self.unlinkLinkNode(key)
        return int(nodeRef.val)

    '''                              
    1. If key not found in cache (first time entry), insert and make it the newest element                               
    2. During insertion if capacity exceeded, then remove the oldest element to make space and then do (1) above       
    3. If key found in cache, then remove the item from the current position and make it the newest element              
    '''
    def set(self, key, value):
        """                              
        :type key: int                              
        :type value: int                               
        :rtype: nothing                               
        """
        if str(key) not in self.dict:
            # if the capacity is reached then delete the tail node (oldest non-referenced node)
            # and make the previous node the current tail
            # also delete the node from the dictionary
            if len(self.dict.keys()) == self.capacity:
                del self.dict[str(self.tail.keyRef)]
                self.tail.prev.next = None
                self.tail = self.tail.prev

            # Now, insert this brand new node towards the head                               
            newNode = Node(str(value), str(key))
            newNode.next = self.head.next
            if self.head.next is not None:
                self.head.next.prev = newNode

            self.head.next = newNode
            newNode.prev = self.head

            # first and only time - keep track of the tail node
            if self.tail == self.head:                              
                self.tail = newNode

            # Also, preserve a reference to this node in a dictionary                              
            self.dict[str(key)] = newNode

        else:
            # Now, take the node from it's exisiting old position and make it current (make it the first node after head)
            # Also, update the new value
            nodeRef = self.unlinkLinkNode(key)
            nodeRef.val = str(value)

    def unlinkLinkNode(self, key):
        # Delete the node from it's existing old position, by relinking pointers of node's prev to node's next  
        nodeRef = self.dict[str(key)]
        nodeRef.prev.next = nodeRef.next
        if nodeRef.next is not None:
            nodeRef.next.prev = nodeRef.prev
        if nodeRef == self.tail and self.tail.prev != self.head:
            self.tail = self.tail.prev

        # Now take the same nodeRef to the head (most recent side), by updating its prev and next pointers               
        nodeRef.next = self.head.next
        if self.head.next is not None:
            self.head.next.prev = nodeRef
        self.head.next = nodeRef
        nodeRef.prev = self.head

        return nodeRef


#1,[set(2,1),get(2),set(3,2),get(2),get(3)]         
#3,[set(1,1),set(2,2),set(3,3),set(4,4),get(4),get(3),get(2),get(1),set(5,5),get(1),get(2),get(3),get(4),get(5)]
#1,[set(2,1),get(2),set(3,2),get(2),get(3)]