Description

A LRU Cache is a system that removes the item that was the least recently accessed. Using a Doubly Linked Lust and a Hash Map you can have O(1) runtime for all operations.

Runtime

O(1)

Visualization

Pseudocode

english

Code

class LRUCache:
    def __init__(self, capacity: int):
        self.lru = None
        self.mru = None
        self.capacity = capacity
        self.data = {}

    def get(self, key: int) -> int:
        if key not in self.data:
            return -1
        else:
            self.remove(self.data[key])
            self.insert(self.data[key])
            return self.data[key].value

    def put(self, key: int, value: int) -> None:
        if key in self.data:
            self.remove(self.data[key])
            del self.data[key]
            
        data = Data(key, value)
        self.data[key] = data
        self.insert(data)
        
        if len(self.data) > self.capacity:
            n = self.lru
            self.remove(n)
            del self.data[n.key]

    def remove(self, n):
        if n is not self.lru and n is not self.mru:
            n.next.prev = n.prev
            n.prev.next = n.next

        elif n is self.lru and n is self.mru:
            self.lru = None
            self.mru = None

        elif n is self.lru:
            self.lru = n.next
            self.lru.prev = None

        elif n is self.mru:
            self.mru = n.prev
            self.mru.next = None

    def insert(self, n):
        if self.lru is None:
            self.mru = n
            self.lru = n
            n.next = None
            n.prev = None
        else:
            self.mru.next = n
            n.prev = self.mru
            self.mru = n