Easy Python Solution using Hash Map and Doubly Linked Lists


#1

class Node:

# Constructor to create a new node 
def __init__(self, key, value): 
    self.next   = None
    self.prev   = None
    self.value  = value
    self.key    = key

class LRUCache:

### FASTER APPROACH ###    

# @param capacity, an integer
def __init__(self, capacity):
    self.hash       =   {}
    self.head       =   None
    self.tail       =   None
    self.size       =   0
    self.capacity   =   capacity

# @return an integer
def get(self, key):
    if self.hash.get(key):
        node    =   self.hash[key]
        # removing and re-adding node so that it will be added at the front of queue
        self.removeNode(node)
        self.addNode(node)
        return node.value
    return -1

# @param key, an integer
# @param value, an integer
# @return nothing
def set(self, key, value):
    if self.hash.get(key) is None:
        node    =   Node(key, value)
        # if node is not exists then adding it at front of the queue
        self.addNode(node)
    else:
        node            =   self.hash[key]
        node.value      =   value
        # if node is already exists then removing and re-adding at front of the queue
        self.removeNode(node)
        self.addNode(node)
        
        
def addNode(self, node):
    if self.size    ==  self.capacity:
        self.removeNode(self.tail)
        
    if self.head is None:
        self.head   =   node
        self.tail   =   node
    else:
        # Adding node at the front of the queue
        self.head.prev  =   node
        node.next       =   self.head
        self.head       =   node
    self.size       +=  1
    self.hash[node.key]  =   node
        
def removeNode(self, node):
    if self.head is node:
        if self.size == 1:
            self.head   =   None
            self.tail   =   None
        else:
            self.head       =   self.head.next
            self.head.prev  =   None
    elif self.tail is node:
        if self.size == 1:
            self.head   =   None
            self.tail   =   None
        else:
            self.tail   =   self.tail.prev
            self.tail.next  =   None
    else:
        node.prev.next  =   node.next
        node.next.prev  =   node.prev
    self.size       -=  1
    del self.hash[node.key]