146. LRU Cache (Hash Table, Linked List, Design, Doubly-Linked List)

링크 - https://leetcode.com/problems/lru-cache/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

LRU Cache문제는 Doubly-Linked List자료구조로 풀 수 있다. 예를 들어, A->B->C->D->E이렇게 캐쉬에 저장되어 있고 C가 호출이 되면 우리는 C를 꺼내서 맨 앞에 넣음으로써 C->A->B->D->E로 만들어서 Cache를 유지할 수 있다.

 

따라서 각 Node는 key, value, next node, prev node를 가지는 클래스로 만들어야 한다.

 

알고리즘은 다음과 같이 작동해야 한다.

1. key-value pair를 저장해야 한다

2. key-value pair를 업데이트 해야 한다

3. key로 조회를 할때, 존재하면 value를 반환하고 없으면 -1를 반환한다.

4. 새로운 key-value pair가 들어오면, doubly-linked list의 맨 앞에 넣는다.

5. 기존의 key-value pair가 조회되면, doubly-linked list안에서 꺼내서 맨 앞에 넣는다.

6. 새로운 key-value pair가 들어왔는데 capacity만큼 용량이 차있으면, 맨 뒤의 노드를 제거해야 한다.

 

이걸 위해, LRU Cache class는 capacity, dic(hash map), head, tail를 가져야 한다. 맨 처음 초기화 할때는 head와 tail를 서로 연결해준다.

Code

class Node:
    
    def __init__(self, key: int, value: int):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None
        
class LRUCache:

    def __init__(self, capacity: int):
        self.hash_table = {}
        self.capacity = capacity
        self.first_node = Node(-1, -1)
        self.last_node = Node(-1, -1)

        self.first_node.next = self.last_node
        self.last_node.prev = self.first_node


    def get(self, key: int) -> int:
        if key not in self.hash_table:
            return -1

        node = self.hash_table.get(key)
        self.remove_node(node)
        self.add_node(node)
        return node.value
        

    def put(self, key: int, value: int) -> None:
        if key in self.hash_table:
            old_node = self.hash_table.get(key)
            self.remove_node(old_node)

        node = Node(key, value)
        self.hash_table[key] = node
        self.add_node(node)

        if len(self.hash_table) > self.capacity:
            node_to_remove = self.last_node.prev
            self.remove_node(node_to_remove)
            del self.hash_table[node_to_remove.key]


    def remove_node(self, node: Node):
        node.prev.next = node.next
        node.next.prev = node.prev


    def add_node(self, node: Node):
        first_next_node = self.first_node.next

        self.first_node.next = node
        node.prev = self.first_node

        node.next = first_next_node
        first_next_node.prev = node

Complexity

Time Complexity: O(1) for both get() and put(). 

 - get(): checking hashmap(O(1)), getting node associated with a key(O(1)), calling remove_node() and add_node()(Both O(1))

 - put(): checking hashmap(O(1)), getting node associated with a key and call remove_node()(both O(1)), create new node and insert it into hash map(O(1)), calling add_node()(O(1)), if the capacity is exceeded, we call remove_node() and delete from the hashmap(Both O(1))

Space Complexity: O(capacity). It's for both hashmap and linkedlist.