LRU Cache

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.

Solution:

LRU(very offen)

Least Recently Used

it's using the data structure 'Double LinkedList + HashMap'

(1)双向链表插入删除效率高（单向链表插入和删除时，还要查找节点的前节点）

(2)哈希表保存每个节点的地址，可以基本保证在O(1)时间内查找节点

When do Get:

if the key is there then delete the duplicate key from Linked List and move it to tail eventually the has table is no change but the dulplicated key will only pointed to the value which is tail and have null node.

when do set

if the key is there then delete the duplicate key then do insert.

LFU

Least Frequently Used

class DoublelyLinkedList:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.prev = self.next = None #made mistake to put as parameters

class LRUCache:

    # @param capacity, an integer
    def __init__(self, capacity):
        self.capacity = capacity
        self.hashmap = {}
        # double dummy head and tail pointer

        self.head = DoublelyLinkedList(-1, -1)
        self.tail = DoublelyLinkedList(-1, -1)

        self.tail.prev = self.head
        self.head.next = self.tail

    # @return an integer
    def get(self, key):
        # write your code here
        if key not in self.hashmap:
            return -1
        #remove the exsiting node and take advantage from dobuledLinkedList
        current = self.hashmap[key] 
        current.prev.next = current.next
        current.next.prev = current.prev
        #add the current node to the tail
        self.addNodeToTail(current)
        # return value
        return self.hashmap[key].value

    # @param key, an integer
    # @param value, an integer
    # @return nothing
    def set(self, key, value):
        # write your code here
        # check if the key exist before insert 
        if self.get(key) != -1:
            self.hashmap[key].value = value
            return
        if len(self.hashmap) >= self.capacity:
            self.hashmap.pop(self.head.next.key) # forget pop node from hashmap
            # the first node is dummy, we will remove the second
            self.head.next = self.head.next.next
            self.head.next.prev = self.head  # delete next node. 

        inserNode = DoublelyLinkedList(key, value)
        self.hashmap[key] = inserNode
        self.addNodeToTail(inserNode)

    def addNodeToTail(self, current):
        current.prev = self.tail.prev
        self.tail.prev = current
        current.prev.next = current
        current.next = self.tail