第二章：LRU算法详解

labuladong LRU算法详解

146. LRU(Least Recently Used) 缓存机制

利用字典+双向链表

• 字典里存的是Node的节点类，self.add(Node(key, value))
• 传给add函数的是一个Node类，这个字典的键是node.key，值是Node类

# 构建Node类
class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None


class LRUCache:

    def __init__(self, capacity):
        # 构建首尾节点, 使之相连
        # 之后处理head到tail之间的node
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

        self.lookup = dict()
        self.max_len = capacity

    def get(self, key):
        if key in self.lookup:
            node = self.lookup[key]
            self.remove(node)
            self.add(node)
            return node.val
        else:
            return -1

    def put(self, key, value):
        if key in self.lookup:
            self.remove(self.lookup[key])# 移除该节点
        if len(self.lookup) == self.max_len:
            # 把表头位置节点删除(说明最近的数据值)
            self.remove(self.head.next)
        self.add(Node(key, value))

    # 删除链表节点
    def remove(self, node):
        del self.lookup[node.key] # 删除该节点
        node.prev.next = node.next # 更新链表
        node.next.prev = node.prev

    # 加在链表尾
    def add(self, node):
        self.lookup[node.key] = node # 添加(key ,node)节点
        pre_tail = self.tail.prev #暂存该节点
        node.next = self.tail #更新链表
        self.tail.prev = node
        pre_tail.next = node
        node.prev = pre_tail