LRU Cache

两道cache经典题中的一道，要求我们按照最近使用的时间来进行列表更新，且要求所有操作时间复杂度O(1)，因为全部都要O(1)，明显我们是需要使用哈希表的，但是因为每次操作都会更新对应的数据位置，也就是说我们必须把最近被操作过的数据放到最不可能被移除的位置去，这个操作又和栈类似，所以明显我们需要一个链表的结构来存储数据，但如果是单链表，则我们虽然可以利用哈希表快速定位，但却无法对结点前后的结点进行正确处理，所以我们需要一个双链表，同时链表的结点里既包含了key，也包含了value，这样方便我们更新时删除结点的操作，最后，凡是链表类的题，dummy node大部分情况都是需要的

class ListNode(object):
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.next = None
        self.prev = None

class LRUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.cap = capacity
        self.root = ListNode('dummy', 'dummy')
        self.curCap = 0
        self.tail = self.root
        self.accesser = {}

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key in self.accesser:
            node = self.accesser[key]
            if self.tail == node:
                return node.val
            self.moveToTail(node)
            return node.val

        return -1

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: void
        """
        if key in self.accesser:
            node = self.accesser[key]
            node.val = value
            if self.tail == node:
                return 
            self.moveToTail(node)
        elif self.curCap < self.cap:
            self.__newNode(key, value)
            self.curCap += 1
        else:
            self.__newNode(key, value)
            del self.accesser[self.root.next.key]
            self.root = self.root.next

    def moveToTail(self, node):
        prevNode = node.prev
        nextNode = node.next
        prevNode.next = nextNode
        nextNode.prev = prevNode
        self.tail.next = node
        node.prev = self.tail
        self.tail = self.tail.next

    def __newNode(self, key, value):
        self.tail.next = ListNode(key, value)
        self.tail.next.prev = self.tail
        self.tail = self.tail.next
        self.accesser[key] = self.tail

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)