本文共 2187 字，大约阅读时间需要 7 分钟。

转载自 

class Node:    # 双向链表中节点的定义    def __init__(self, k, x):        self.key = k        self.val = x        self.prev = None        self.next = Noneclass DoubleLinkedList:    # 双向链表是一个表头，head指向第一个节点，tail指向最后一个节点    def __init__(self):        self.tail = None        self.head = None    def isEmpty(self):        # 如果self.tail==None，那么说明双向链表为空        return not self.tail    def removeLast(self):        # 删除tail指向的节点        self.remove(self.tail)    def remove(self, node): # 具体双向链表节点删除操作的实现        if self.head == self.tail:            self.head, self.tail = None, None            return        if node == self.head:            node.next.prev = None            self.head = node.next            return        if node == self.tail:            node.prev.next = None            self.tail = node.prev            return        node.prev.next = node.next        node.next.prev = node.prev    def addFirst(self, node):        # 在双向链表的第一个节点前面再插入一个节点　　        if not self.head:            self.head = self.tail = node            node.prev = node.next = None            return        node.next = self.head        self.head.prev = node        self.head = node        node.prev = Noneclass LRUCache:    # @param capacity, an integer    def __init__(self, capacity):        # 初始化LRU Cache        self.capacity = capacity        self.size = 0        self.P = dict()        self.cache = DoubleLinkedList()    # @return an integer    def get(self, key):     # 查询操作        if (key in self.P) and self.P[key]:            self.cache.remove(self.P[key])            self.cache.addFirst(self.P[key])            return self.P[key].val        else: return -1    # @param key, an integer    # @param value, an integer    # @return nothing    def set(self, key, value):        if key in self.P:            self.cache.remove(self.P[key])            self.cache.addFirst(self.P[key])            self.P[key].val = value        else:            node = Node(key, value)            self.P[key] = node            self.cache.addFirst(node)            self.size += 1            if self.size > self.capacity:                self.size -= 1                del self.P[self.cache.tail.key]                self.cache.removeLast()