https://leetcode.com/problems/lru-cache/submissions/1221683044/?envType=study-plan-v2&envId=top-interview-150

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

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.dic = {}
        self.head = ListNode(-1, -1)
        self.tail = ListNode(-1, -1)
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        if key not in self.dic:
            return -1
        
        node = self.dic[key]
        # remove the node from it's existing place
        # and add it to the end of the linked list
        self.remove(node)
        self.add(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        # if key already exists
        if key in self.dic:
            # get the old node and remove it from the linked list
            old_node = self.dic[key]
            self.remove(old_node)
        
        # create new node, add the key:key node pairing to dictionary,
        # and add node to end of linked list
        node = ListNode(key, value)
        self.dic[key] = node
        self.add(node)

        # if adding new node exceeds capacity
        if len(self.dic) > self.capacity:
            # get the node at the front of the linked list
            node_to_delete = self.head.next
            # delete it from the list
            self.remove(node_to_delete)
            # delete it from the dictionary
            del self.dic[node_to_delete.key]

    def add(self, node):
        # get the node at the end of the linked list
        previous_end = self.tail.prev
        # insert new node after the previous end node 
        previous_end.next = node
        # set the prev and next of new end node
        node.prev = previous_end
        node.next = self.tail
        # update the prev of the tail to be the new end node
        self.tail.prev = node

    def remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

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

struct Node {
    int key;
    int val;
    Node *next;
    Node *prev;
    Node(int key, int val) : key(key), val(val), next(nullptr), prev(nullptr) {}
};

class LRUCache {
public:
    int capacity;
    unordered_map<int, Node*> dic;
    Node *head = new Node(-1, -1);
    Node *tail = new Node(-1, -1);
    LRUCache(int capacity) {
        this->capacity = capacity;
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        if (dic.find(key) == dic.end()){
            return -1;
        }

        Node *node = dic[key];
        remove(node);
        add(node);
        return node->val;
    }
    
    void put(int key, int value) {
        if (dic.find(key) != dic.end()){
            Node *oldNode = dic[key];
            remove(oldNode);
        }

        Node *node = new Node(key, value);
        dic[key] = node;
        add(node);

        if (dic.size() > capacity) {
            Node *nodeToDelete = head->next;
            remove(nodeToDelete);
            dic.erase(nodeToDelete->key);
        }
    }

    void add(Node *node) {
        Node *previousEnd = tail->prev;
        previousEnd->next = node;
        node->prev = previousEnd;
        node->next = tail;
        tail->prev = node;
    }

    void remove(Node *node){
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

The LRU Cache implementation has the following time and space complexities:

Time Complexity:

• get() operation: O(1)
• put() operation: O(1)

Space Complexity: O(capacity)

This efficient performance is achieved by using:

• A hashmap (dictionary) for O(1) key lookups
• A doubly linked list for O(1) node removal and addition operations
• The space is limited to storing at most 'capacity' number of key-value pairs in both the hashmap and linked list