링크드 리스트(LRU cache)

LRU cache 문제는 key-value를 저장하는 자료구조를 만드는 문제이다.

put(key, value)로 저장하고 get(key)로 value를 리턴한다.

 

자료구조를 만들 때 max size를 설정하는데, 저장개수가 이 보다 크면 저장 데이터 한 개를 지우고 저장한다.

데이터를 지울 때는 규칙이 있다. Least Recently Used 즉, 가장 오래전에 사용한 데이터를 지운다. 문제이름 LRU cache는 지우는 규칙을 가리킨다.

 

 

사용한 순서를 알기 위해서 array를 사용할 수 있다. 그러나 array는 가장 먼저 사용한 아이템을 지우고 빈 자리를 메워야하는 제약때문에 O(n) time complexity가 필요하다. 문제에서 원하는 time complexity는 O(1)이다.

 

 

doubly linked list를 사용하면 문제를 해결할 수 있다.

 

# Title : LRU cache 구현하기
# Chapter : Linked List
# 문제 : Least Recently Used (LRU) cache를 구현하여라

class ListNode:
    def __init__(self, key:int, value:int) -> None:
        self.key = key
        self.val = value
        self.left = None
        self.right = None

class LRUCache:
    def __init__(self, capacity: int) -> None:
        self._max_cap = capacity
        self._hashmap = {}
        self._list_head = ListNode(-1, -1)
        self._list_tail = ListNode(-1,-1)
        self._list_head.right = self._list_tail
        self._list_tail.left = self._list_head

    def get(self, key:int) -> int:
        value_node = self._hashmap.get(key)
        if value_node:
            self._removeFromList(value_node)
            self._addBack(value_node)
            return value_node.val
        else:
            return -1

    def put(self, key:int, val:int)->None:
        value_node = self._hashmap.get(key)
        if value_node:
            value_node.val = val
            self._removeFromList(value_node)
            self._addBack(value_node)
            return
        
        value_node = ListNode(key, val)
        self._addBack(value_node)
        self._hashmap[key] = value_node

        if self._max_cap < len(self._hashmap):
            lru_node = self._list_head.right
            lru_key = lru_node.key
            self._removeFromList(lru_node)
            self._hashmap.pop(lru_key)
        

    def _removeFromList(self, node:ListNode) -> None:
        left_node = node.left
        right_node = node.right
        left_node.right = right_node
        right_node.left = left_node

    def _addBack(self, node:ListNode) -> None:
        tail_left = self._list_tail.left

        tail_left.right = node
        node.left = tail_left

        node.right = self._list_tail
        self._list_tail.left = node

lru_cache = LRUCache(4)
lru_cache.put(1,10)
lru_cache.put(2,20)
lru_cache.put(3,30)
lru_cache.put(4,40)
print(1,lru_cache.get(1)) #key 1 renew

lru_cache.put(5,50)
print(1,lru_cache.get(1))
print(2,lru_cache.get(2))
print(3,lru_cache.get(3))
print(4,lru_cache.get(4))
print(5,lru_cache.get(5))

 

 

참조 : (3) 코딩 테스트, 중급, LRU cache - YouTube