146. LRU Cache

Question

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Example 1

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

Solution 1: Double Linked List

Time Complexity: O()
Space Complexity: O()

Solution 2: Double Linked List + Hash

# Combine Double Link List + HashSet
class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    ######## After Init ##########
    #
    # ←←←←←←                ←←←←←←
    # ↓→→→→Tail→NotUsed←Head→→→→↓↑
    # ↓↑                        ↓↑
    # ↓↑←←←←←←←←←←←←←←←←←←←←←←←←↓↑
    # ↓→→→→→→→→→→→→→→→→→→→→→→→→→→↑
    #
    ##############################
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.hash = {} # (key, Node)
        self.head = Node(-1, None)
        self.tail = Node(-1, None)
        
        ### Tail point to the latest Node & Head to the oldest
        # self.head.prev # Not Used
        self.head.next = self.tail # Dummy Head
        self.tail.prev = self.head # Dummy Tail
        # self.tail.next # Not Used

    def get(self, key: int) -> int:
        if key not in self.hash:
            return -1
        
        node = self.hash[key]
        self._removeNode(node)
        self._addTailNode(node)
        return node.val
        
    def put(self, key: int, value: int) -> None:
        if key in self.hash:
            self._removeNode(self.hash[key])
            
        node = Node(key, value)
        self._addTailNode(node)
        self.hash[key] = node
        if len(self.hash) > self.capacity:
            self._evict()
    
    ### Self-Defined
    def _removeNode(self, node):
        node.prev.next, node.next.prev = node.next, node.prev 

    def _addTailNode(self, node):
        lastValidNode = self.tail.prev
        lastValidNode.next = node
        node.prev = lastValidNode
        self.tail.prev = node # lastValidNode = node
        node.next = self.tail
        
    def _evict(self):
        node = self.head.next # the least recently used node
        self._removeNode(node)
        self.hash.pop(node.key) # update hash (Remove)

For both Get & Put operation:
Time Complexity: O(1)
Space Complexity: O(N)

Solution 3: Double Linked List + OrderedHash

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.listCache = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.listCache:
            return -1
        
        # Recently used, move to tail
        self.listCache.move_to_end(key)
        return self.listCache[key]
        
        
    def put(self, key: int, value: int) -> None:
        if key in self.listCache:
            del self.listCache[key]
            
        self.listCache[key] = value
        if len(self.listCache) > self.capacity:
            # Evict: Remove the head (Least recently used))
            self.listCache.popitem(last=False)

For both Get & Put operation:
Time Complexity: O(1)
Space Complexity: O(N)

Reference

https://www.geeksforgeeks.org/lru-cache-implementation-using-double-linked-lists/?ref=rp
https://www.geeksforgeeks.org/lru-cache-implementation/
https://leetcode.com/problems/lru-cache/discuss/45926/Python-Dict-%2B-Double-LinkedList

Python OrderedDict
https://ithelp.ithome.com.tw/articles/10193794

Follow-up: LFU Cache

Follow-up 2: Design In-Memory File System