Description

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.
Finally, you need to return the data from each get.

Solution

实现两个函数，课使用linked list 但是实现时需要有hashdict存prev node （注意还需考虑多次set）

class Node:
    
    def __init__(self, key=None, val=None, next=None):
        self.key = key
        self.val = val
        self.next = next

class LRUCache:
    """
    @param: capacity: An integer
    """
    def __init__(self, capacity):
        # do intialization if necessary
        self.capacity = capacity
       
        self.head = Node() # dummy head
        self.tail = self.head
        self.prev={} # <node add: prev_node add>
        
    def push_back(self,node):
        self.tail.next = node
        self.prev[node.key] = self.tail
        self.tail = node
        node.next = None
    
    def kick(self,node):
        if node == self.tail:
            return
        prev = self.prev[node.key]
        prev.next = node.next
        if node.next is not None:
            self.prev[node.next.key] = prev
        self.push_back(node)
       
    
    def pop_front(self):
        
        node = self.head.next
        
        self.head.next = node.next
        # if node.next is not None:
        self.prev[node.next.key] = self.head
        del self.prev[node.key]
        # del node
    
    """
    @param: key: An integer
    @return: An integer
    """
    def get(self, key):
        # write your code here
     
        if key in self.prev:
           
            self.kick( self.prev[key].next)
            return self.prev[key].next.val
        else:
            
            return -1
    
    """
    @param: key: An integer
    @param: value: An integer
    @return: nothing
    """
    def set(self, key, value):
        # write your code here\
        if key in self.prev:
            self.kick(self.prev[key].next)
            self.prev[key].next.val = value ## important
            return
        
        self.push_back(Node(key,value,None))
        if len(self.prev) > self.capacity:
            self.pop_front()