题解 | #设计LRU缓存结构#

class DlinkNode:
# 构造双向链表
    def __init__(self, key=0, value=0):  
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class Solution:
"""
1、构造双向链表，越靠近头部的节点表示越常被访问
2、构造哈希表，哈希表中的每个键都指向当前双向链表中的一个节点
3、等价划分几种情况：
    （1）get操作，访问key值不存在。直接返回-1
    （2）get操作，访问key值存在。通过哈希表寻找到对应的节点，返回节点值。将被访问节点挪到头节点
    （3）set操作（这里用put函数表示），key值不存在。生成节点（key，value），并将其添加到头节点
    （4）set操作，key值存在。通过哈希表拿到key值所指向的node，并更新其value值，将其添加到头节点

"""
    def __init__(self):
        self.hash = dict()   # 哈希字典，存储当前所指向的键值对
        self.size = 0  # 初始化链表长度为0
        self.res = []  # 初始化返回结果为空

        self.head = DlinkNode()  # 构造头伪节点
        self.tail = DlinkNode()  # 构造尾伪节点
        # 构造伪节点的作用在于防止链表为空，节点访问出现问题

        self.head.next = self.tail  # 构造双向链表
        self.tail.prev = self.head

    def LRU(self , operators , k):
        self.capacity = k  # 初始化链表容量为k

        for i in range(len(operators)):
            opt = operators[i][0]  # 确定操作数为1、2；分别进入get和put函数。
            key = operators[i][1]  # 无论操作数是1、2，key值都是operators[i][1]
            if opt==2:  # 操作数为2时，进行get操作
                tmp = self.get(key)
                self.res.append(tmp)  
            else:  # 进行put操作
                value = operators[i][2]
                self.put(key, value)
        return self.res

    def get(self, key):
        if key not in self.hash:  # 当前待访问的键不存在，返回-1
            return -1
        node = self.hash[key]  # 存在则通过哈希表找到这个节点
        self.movetoHead(node)  # 将当前被访问的节点移动到头部，成为最常被访问的节点
        return node.value

    def put(self, key, value):
        if key not in self.hash:  # 不存在，新建节点，添加到头部，哈希表中也要添加对应的节点
            node = DlinkNode(key, value)
            self.addtoHead(node)
            self.hash[key] = node # 哈希表中添加对应的节点
            self.size += 1
            if self.size > self.capacity: # 避免节点容量问题
                removed = self.removeTail()
                self.hash.pop(removed.key)
                self.size -= 1
        else:  # 存在，更新value值
            node = self.hash[key]
            node.value = value
            self.movetoHead(node)

    def moveNode(self, node): # 删除某节点
        node.next.prev = node.prev
        node.prev.next = node.next
        node.next = None
        node.prev = None

    def addtoHead(self, node): # 新节点添加到头部
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def movetoHead(self, node): # 原来的节点移动到头部
        self.moveNode(node)
        self.addtoHead(node)

    def removeTail(self): # 删除掉末尾的节点
        node = self.tail.prev
        self.moveNode(node)
        return node

    # write code here