LRUCache的两种写法（Python）

LeetCode链接

手动实现双向链表 + dict 时间复杂度 get put O(1)

class Node:
    def __init__(self, k=0, v=0):
        self.k = k
        self.v = v
        self.next = None
        self.prev = None

class LRUCache:

    def __init__(self, capacity: int):
        # dict 的value存储链表的node节点
        self.data = {}
        self.capacity = capacity
        self.size = 0
        # 虚拟头尾节点
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        if key in self.data:
            n = self.data[key]
            # 将节点移动至尾部
            self._remove(n)
            self._add(n)
            return n.v
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.data:
            n = self.data[key]
            n.v = value
            # 将节点移动至尾部
            self._remove(n)
            self._add(n)
        else:
            n = Node(key, value)
            self.data[key] = n
            self._add(n)
            self.size += 1
            if self.size > self.capacity:
                n_to_remove = self.head.next
                self._remove(n_to_remove)
                # 记得把对应的键清除
                self.data.pop(n_to_remove.k)    

    def _remove(self, n: Node):
        n_prev = n.prev
        n_next = n.next
        n_prev.next = n_next
        n_next.prev = n_prev
    
    def _add(self, n: Node):
        """
        此处add始终在尾部添加 配合_remove可以把常用的节点移动到链表的尾部
        自然，头部就是最不经常使用的节点，长度超限，删除之即可
        """
        tail_prev = self.tail.prev
        tail_prev.next = n
        n.prev = tail_prev
        n.next = self.tail
        self.tail.prev = n

基于已有的 collections.OrderedDict

class LRUCache(collections.OrderedDict):

    def __init__(self, capacity: int):
        super().__init__()
        self.capacity = capacity


    def get(self, key: int) -> int:
        if key not in self :
            return -1
        self.move_to_end(key)
        return self[key]

    def put(self, key: int, value: int) -> None:
        if key in self:
            self.move_to_end(key)
        self[key] = value
        if len(self) > self.capacity:
            self.popitem(last=False)