Python solution using doubly linkedlist and Hash table


#1

Comment body goes here.`
class Node:
def init(self,_key,_val):
self.key = _key
self.val = _val
self.next = None
self.prev = None

class LRUCache:

# @param capacity, an integer
def __init__(self, capacity):
    self.capacity= capacity
    self.dict = dict()
    self.head = Node(0,0)
    self.tail = Node(0,0)
    self.head.next = self.tail
    self.tail.prev = self.head
    self.counter = 0
# @return an integer
def get(self, key):
    if key not in self.dict:
        return -1
    else:
        node = self.dict[key]
        self.remove(node)
        self.add(node)
        return node.val
# @param key, an integer
# @param value, an integer
# @return nothing
def set(self, key, value):
    if key not in self.dict:
        node = Node(key,value)
        self.dict[key] = node
        self.add(node)
        self.counter += 1
    else:
        node = self.dict[key]
        node.val = value
        self.remove(node)
        self.add(node)
    if(self.counter > self.capacity):
        todel = self.tail.prev
        self.remove(todel)
        del self.dict[todel.key]
        self.counter -= 1
 ## to add recently used member to the cache
def add(self,node):
    temp = self.head.next
    self.head.next = node
    node.prev = self.head
    node.next = temp
    temp.prev = node
## to remove the LRU member
def remove(self,node):
    before = node.prev
    after = node.next
    before.next = after
    after.prev = before

`