LRU的Python双向链表实现

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。

写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

分析
看到题目要我们实现一个可以存储 key-value 形式数据的数据结构，并且可以记录最近访问的 key 值。首先想到的就是用字典来存储 key-value 结构，这样对于查找操作时间复杂度就是 O(1)O(1)。

但是因为字典本身是无序的，所以我们还需要一个类似于队列的结构来记录访问的先后顺序，这个队列需要支持如下几种操作：

在末尾加入一项
去除最前端一项
将队列中某一项移到末尾

考虑单链表。

对于单链表，哈希表的结构类似于 {key: ListNode(value)}，即键所对应的是一个节点地址，节点的值是 value。对于链表，遇到上面那种情况时可以在常数的时间内找到对应的节点，但是如果想将它移到尾部则需要从头遍历到该节点才能保证链表不断，对于这种情况需要的时间复杂度也是O(n)

为了解决移到末尾这个问题，需要使用双链表来记录

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


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.hashmap = {}
        # 新建两个节点
        self.head = ListNode()
        self.tail = ListNode()
        # 初始化链表为head<->tail
        self.head.next = self.tail
        self.tail.pre = self.head

    # 因为get和put操作都可能将双向链表中的某个节点移到末尾，所以定义一个新的方法
    def move_node_to_tail(self, key):
        node = self.hashmap[key]
        node.pre.next = node.next
        node.next.pre = node.pre
        # 将node插入到尾结点之前
        node.pre = self.tail.pre
        node.next = self.tail
        self.tail.pre.next = node
        self.tail.pre = node

    def get(self, key:int) -> int:
        if key in self.hashmap:
            # 如果已经存在 把该node移到尾部 最新访问
            self.move_node_to_tail(key)
        res = self.hashmap.get(key, -1)
        if res == -1:
            return res
        else:
            return res.val

    def put(self, key: int, val: int) -> None:
        if key in self.hashmap:
            # 如果已经存在 则将原有的直接移动到末尾 需要更新原有的hash值
            self.hashmap[key].val = val
            self.move_node_to_tail(key)
        else:
            if len(self.hashmap) == self.capacity:
                # 去掉hash对应项
                self.hashmap.pop(self.head.next.key)
                # 去掉最久没有被访问过的节点，即头节点之后的节点
                self.head.next = self.head.next.next
                self.head.next.pre = self.head
            # 如果列表没有满 直接插入到尾部
            new = ListNode(key, val)
            new.pre = self.tail.pre
            new.next = self.tail
            self.tail.pre.next = new
            self.tail.pre = new