数据类型：链表
时间复杂度：O(1)文章来源：https://www.toymoban.com/news/detail-800686.html
空间复杂度：O(N)文章来源地址https://www.toymoban.com/news/detail-800686.html
代码实现：
class Node:
def __init__(self, key=-1, value=-1):
self.key = key
self.val = value
self.next = None
self.prev = None
class LRUCache:
def __init__(self, capacity: int):
self.map = dict()
self.cap = capacity
self.left = Node()
self.right = Node()
self.right.prev = self.left
self.left.next = self.right
def pop(self, node: Node):
node.prev.next, node.next.prev = node.next, node.prev
def push(self, node: Node):
last = self.right.prev
last.next = node
node.prev, node.next = last, self.right
self.right.prev = node
def get(self, key: int) -> int:
if key not in self.map: return -1
self.pop(self.map[key])
self.push(self.map[key])
return self.map[key].val
def put(self, key: int, value: int) -> None:
if key in self.map:
self.pop(self.map[key])
elif self.cap == len(self.map):
self.map.pop(self.left.next.key)
self.pop(self.left.next)
self.push(Node(key, value))
self.map[key] = self.right.prev
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)到了这里，关于（力扣记录）146. LRU 缓存的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
