LinkedList : LRU Cache (Singly Linked List 해법)

https://leetcode.com/problems/lru-cache/description/

LRU Cache - LeetCode

 

링크드리스트로 LRU 키 리스트를 관리하면 풀수있다.

근데 엣지케이스랑 dict 키값에 숫자를 안넣고 노드를 넣는등 이상한 실수를 하는 바람에 30분만에 풀어야되는걸 2시간걸려 풀었다.

class Node:
    def __init__(self, key = None, next = None):
        self.key = key
        self.next = next

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.lru_list_front = self.lru_list_rear = Node()
        self.key_to_prev_node = {}

    def add_to_lru_list(self, key:int) -> None:
        self.lru_list_rear.next = Node(key)
        self.key_to_prev_node[key] = self.lru_list_rear
        self.lru_list_rear = self.lru_list_rear.next

    def delete_from_lru_list(self, key:int) -> None:
        prev_node = self.key_to_prev_node[key]
        if prev_node.next.next:
            self.key_to_prev_node[prev_node.next.next.key] = prev_node
        else:
            self.lru_list_rear = prev_node
        self.key_to_prev_node.pop(key)
        prev_node.next = prev_node.next.next

    def remove_key(self, key):
        self.cache.pop(key)

    def pop_lru_key(self):
        lru_key = self.lru_list_front.next.key
        self.delete_from_lru_list(lru_key)
        return lru_key

    def exists(self, key) -> bool:
        return key in self.cache

    def full(self) -> bool:
        return len(self.cache) == self.capacity

    def get(self, key: int) -> int:
        if self.exists(key):
            self.delete_from_lru_list(key)
            self.add_to_lru_list(key)
            return self.cache[key]
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if self.exists(key):
            self.delete_from_lru_list(key)

        self.add_to_lru_list(key)

        if not self.exists(key) and self.full():
            self.remove_key(self.pop_lru_key())

        self.cache[key] = value