[LeetCode] 146. LRU Cache

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

Use doubly linked list to save order of inserted value node.

Most recently used node is on the tail of the doubly linked list.

Least recently used node is no the head of the doubly linked list.

Use dictionary to save the added value and its related linked list node.

Time complexity  = O ( 1 )

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

class LRUCache:
    def __init__(self, capacity: int):
        self.memo = {}
        self.queue = Node(-1)
        self.tail = self.queue
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key in self.memo:
            val, node = self.memo[key]
            
            self._remove(node)
            self._append(node)

            return val
        
        return -1
        
    def put(self, key: int, value: int) -> None:
        if key in self.memo:
            _, node = self.memo[key]
         
            self.memo[key] = (value, node)
            self._remove(node)
            self._append(node)
        elif len(self.memo) < self.capacity:
            node = Node(key)
            self.memo[key] = (value, node)
            self._append(node)
        else:
            removed = self._popleft()
            del self.memo[removed.key]
            
            node = Node(key)
            self.memo[key] = (value, node)
            self._append(node)
    
    def _remove(self, node):
        if node == self.tail:
            self.tail = node.pre
        
        pre_node = node.pre
        next_node = node.next
        
        pre_node.next = next_node
        if next_node:
            next_node.pre = pre_node
            
    def _append(self, node):
        self.tail.next = node
        node.pre = self.tail
        node.next = None
        
        self.tail = node
    
    def _popleft(self):
        node = self.queue.next
        if node:
            self.queue.next = node.next
            if node.next:
                node.next.pre = self.queue
            
            if self.tail == node:
                self.tail = node.pre
        
        return node


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)