LRU Cache

class ListNode(object):
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None


class LRUCache:

    def __init__(self, capacity: int):
        self.head = ListNode(-1, -1) # 新しいほう
        self.tail = ListNode(-2,-2) # 古いほう
        self.cache = dict() # nodeがval
        self.head.next = self.tail
        self.tail.prev = self.head
        self.capacity = capacity
        self.length = 0
        
        
    # 先頭にnodeを追加
    def add(self, node):
        
        node.prev = self.head
        node.next = self.head.next
        self.head.next = node
        node.next.prev = node
        
    # 削除
    def remove(self, node):
        node.prev.next, node.next.prev = node.next, node.prev

    # 一回削除してから先頭に足す。増えないのでcapacityを超えることはない
    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        
        node = self.cache[key]
        self.remove(node)
        self.add(node)
        return node.val
        

    def put(self, key: int, value: int) -> None:
        # 既にキャッシュ内に存在するならgetとほぼ同じ
        if key in self.cache:
            node = self.cache[key]
            node.val = value
            self.remove(node)
            self.add(node)
        # ないならcapacityを超える場合はtailに最も近いものを削除してから追加
        else:
            if len(self.cache) == self.capacity:
                tail_node = self.tail.prev
                del self.cache[tail_node.key]
                self.remove(tail_node)
            
            node = ListNode(key, value)
            self.cache[key] = node
            self.add(node)

collections.OrderedDictを使うと非常にスッキリする

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.dic = collections.OrderedDict()
        
    
    def get(self, key):
        if key not in self.dic:
            return -1
        
        val = self.dic[key]
        self.dic.move_to_end(key) # 後ろのものほど新しい
        return val
    

    def put(self, key, value):
        self.dic[key] = value
        self.dic.move_to_end(key)
        if len(self.dic) > self.capacity:
            # last=Trueなら末尾（最も新しく利用したもの）を、Falseなら先頭のkey,valueを削除
            self.dic.popitem(last=False)

参考
medium.com

leetcode.com