LinkedList : LRU Cache (Doubly Linked List 해법)

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

LRU Cache - LeetCode

 

이번에는 양방향 연결 리스트를 이용해 풀어봤다.

양방향 연결 리스트를 이용하면 조금 쉬울줄 알았으나 역시 이것저것 헷갈리고 실수하는 것들 때문에 꽤 어려웠다.

푸는데 30분 걸려야되는데 1시간이 걸렸다.

 

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

    def delete(self):
        prev = self.prev
        next = self.next
        if prev:
            prev.next = next
        if next:
            next.prev = prev

class List:
    def __init__(self):
        self.front = self.rear = Node()
        self.length = 0

    def add_rear(self, val):
        self.length += 1
        node = Node(val, prev=self.rear)
        self.rear.next = node
        self.rear = node
        return node
    
    def pop_rear(self):
        self.length -= 1
        val = self.rear.val
        prev = self.rear.prev
        prev.next = None
        self.rear = prev
        return val

    def add_front(self, val):
        self.length += 1
        node = Node(val)
        first = self.front.next
        node.next = first
        node.prev = self.front
        first.prev = node
        self.front.next = node
        return node

    def pop_front(self):
        self.length -= 1
        first = self.front.next
        val = first.val
        second = first.next
        if second:
            second.prev = self.front
        else:
            self.rear = self.front
        self.front.next = second
        return val

    def get_length(self):
        return self.length

    def is_empty(self):
        return self.length == 0

    def delete_node(self, node):
        if node == self.rear:
            self.rear = self.rear.prev
        node.delete()
        self.length -= 1


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.key2node = {}
        self.lru_list = List()

    def _add_key(self, key):
        new_node = self.lru_list.add_rear(key)
        self.key2node[key] = new_node

    def _update(self, key):
        node = self.key2node[key]
        self.lru_list.delete_node(node)
        self._add_key(key)

    def _remove(self, key):
        self.key2node.pop(key)
        self.cache.pop(key)
    
    def get(self, key: int) -> int:
        if key in self.cache:
            self._update(key)
            return self.cache[key]
        else:
            return -1

    def put(self, key: int, val: int) -> None:
        if key in self.cache:
            self._update(key)
        else:
            if self.lru_list.get_length() == self.capacity:
                old_front = self.lru_list.pop_front()
                self._remove(old_front)
            self._add_key(key)

        self.cache[key] = val