146. LRU Cache

1import java.util.HashMap;
2import java.util.Map;
3
4// Definition for a doubly linked list node
5class DoublyLinkedNode {
6    int key;
7    int value;
8    DoublyLinkedNode prev;
9    DoublyLinkedNode next;
10
11    // Constructor for creating a new node with key and value
12    public DoublyLinkedNode(int key, int value) {
13        this.key = key;
14        this.value = value;
15    }
16}
17
18// LRUCache class implementing LRU caching mechanism
19public class LRUCache {
20    private final Map<Integer, DoublyLinkedNode> cacheMap; // Hash map to store key-node pairs for O(1) access
21    private final DoublyLinkedNode head;                   // Dummy head of the doubly linked list
22    private final DoublyLinkedNode tail;                   // Dummy tail of the doubly linked list
23    private final int capacity;                            // Maximum capacity of the cache
24    private int size;                                      // Current size of the cache
25
26    // Constructor to initialize the LRU cache
27    public LRUCache(int capacity) {
28        this.capacity = capacity;
29        this.cacheMap = new HashMap<>();
30        this.size = 0;
31        head = new DoublyLinkedNode(0, 0);
32        tail = new DoublyLinkedNode(0, 0);
33        head.next = tail; // Initially, the dummy head points to the dummy tail
34        tail.prev = head; // and the dummy tail points back to the dummy head
35    }
36
37    // Retrieves the value of the node associated with the given key
38    public int get(int key) {
39        if (!cacheMap.containsKey(key)) {
40            return -1;
41        }
42        DoublyLinkedNode node = cacheMap.get(key);
43        moveToHead(node); // Move the accessed node to the head to maintain LRU order
44        return node.value;
45    }
46
47    // Adds a new key-value pair to the cache or updates the value if it already exists
48    public void put(int key, int value) {
49        if (cacheMap.containsKey(key)) {
50            DoublyLinkedNode node = cacheMap.get(key);
51            node.value = value;
52            moveToHead(node); // Move the updated node to the head
53        } else {
54            DoublyLinkedNode newNode = new DoublyLinkedNode(key, value);
55            cacheMap.put(key, newNode);
56            addToHead(newNode); // Add the new node to the head of the linked list
57            size++;
58            if (size > capacity) {
59                DoublyLinkedNode tail = removeTail(); // Remove the least recently used node
60                cacheMap.remove(tail.key); // Also remove it from the map
61                size--;
62            }
63        }
64    }
65
66    // Moves a node to the head of the doubly linked list (marks it as recently used)
67    private void moveToHead(DoublyLinkedNode node) {
68        removeNode(node); // Remove the node from its current position
69        addToHead(node); // Add it back to the head
70    }
71
72    // Removes a node from the doubly linked list
73    private void removeNode(DoublyLinkedNode node) {
74        node.prev.next = node.next;
75        node.next.prev = node.prev;
76    }
77
78    // Adds a node right after the dummy head node (marks it as recently used)
79    private void addToHead(DoublyLinkedNode node) {
80        node.next = head.next;
81        node.prev = head;
82        head.next.prev = node;
83        head.next = node;
84    }
85
86    // Removes and returns the tail node (least recently used node)
87    private DoublyLinkedNode removeTail() {
88        DoublyLinkedNode res = tail.prev;
89        removeNode(res);
90        return res;
91    }
92}
93
94// The usage of LRUCache class would be the same as before, following the given interface.
95

1#include <unordered_map>
2
3// Node structure representing a doubly linked list node
4struct Node {
5    int key;
6    int value;
7    Node* prev;
8    Node* next;
9
10    // Constructor initializes a generic node
11    Node()
12        : key(0)
13        , value(0)
14        , prev(nullptr)
15        , next(nullptr) {}
16
17    // Constructor initializes a node with a specified key and value
18    Node(int key, int value)
19        : key(key)
20        , value(value)
21        , prev(nullptr)
22        , next(nullptr) {}
23};
24
25// LRUCache class representing a Least Recently Used (LRU) cache
26class LRUCache {
27public:
28    // Constructor to create a cache with a specific capacity
29    LRUCache(int capacity)
30        : capacity(capacity)
31        , size(0) {
32        head = new Node(); // Sentinel head node
33        tail = new Node(); // Sentinel tail node
34        head->next = tail; // Connect head to tail
35        tail->prev = head; // Connect tail to head
36    }
37
38    // Returns the value of the node with the given key, if it exists
39    int get(int key) {
40        if (!cache.count(key)) return -1; // Key not found, return -1
41        Node* node = cache[key];
42        moveToHead(node); // Move node to head to mark as recently used
43        return node->value;
44    }
45
46    // Add or update the value of the node with the given key
47    void put(int key, int value) {
48        if (cache.count(key)) { // If the key is found, update the node
49            Node* node = cache[key];
50            node->value = value;
51            moveToHead(node); // Move node to head as it's recently used
52        } else { // Key not found, need to insert a new node
53            Node* node = new Node(key, value);
54            cache[key] = node; // Add to the map
55            addToHead(node); // Add node to the doubly linked list as the most recently used
56            ++size;
57
58            // If over capacity, remove the least recently used item
59            if (size > capacity) {
60                node = removeTail();
61                cache.erase(node->key); // Remove from the cache map
62                delete node; // Delete the node to prevent memory leak
63                --size;
64            }
65        }
66    }
67
68private:
69    std::unordered_map<int, Node*> cache; // Cache storage
70    Node* head; // Head of the doubly linked list
71    Node* tail; // Tail of the doubly linked list
72    int capacity; // The capacity of the cache
73    int size; // The current size of the cache
74
75    // Move a node to the head of the doubly linked list
76    void moveToHead(Node* node) {
77        removeNode(node);
78        addToHead(node);
79    }
80
81    // Remove a node from the doubly linked list
82    void removeNode(Node* node) {
83        node->prev->next = node->next;
84        node->next->prev = node->prev;
85    }
86
87    // Insert a node right after the head node
88    void addToHead(Node* node) {
89        node->next = head->next;
90        node->prev = head;
91        head->next->prev = node;
92        head->next = node;
93    }
94
95    // Remove the tail node (the least recently used node)
96    Node* removeTail() {
97        Node* node = tail->prev;
98        removeNode(node);
99        return node;
100    }
101};
102
103/**
104 * Your LRUCache object will be instantiated and called as such:
105 * LRUCache* obj = new LRUCache(capacity);
106 * int param_1 = obj->get(key);
107 * obj->put(key,value);
108 */
109

1// Define the capacity and storage for the LRU cache
2let lruCapacity: number;
3let lruMap: Map<number, number>;
4
5/**
6 * Initializes the LRU Cache with a specified capacity.
7 * @param capacity - the number of items the cache can hold
8 */
9function initializeLRUCache(capacity: number): void {
10    lruCapacity = capacity;
11    lruMap = new Map();
12}
13
14/**
15 * Retrieves the value associated with the given key and updates the cache to reflect recent access.
16 * Returns -1 if the key is not present in the cache.
17 * @param key - the key whose associated value is to be returned
18 * @return the value associated with the key, or -1 if the key does not exist
19 */
20function getFromLRUCache(key: number): number {
21    if (lruMap.has(key)) {
22        const val = lruMap.get(key)!;
23        // Move the key to the end to show it was recently accessed
24        lruMap.delete(key);
25        lruMap.set(key, val);
26        return val;
27    }
28    return -1;
29}
30
31/**
32 * Inserts or updates the value associated with the key in the cache.
33 * If the cache exceeds its capacity, the least recently used (LRU) entry is removed.
34 * @param key - the key with which the specified value is to be associated
35 * @param value - the value to be associated with the specified key
36 */
37function putIntoLRUCache(key: number, value: number): void {
38    // If the value is already in the cache, delete it so we can update the access order
39    if (lruMap.has(key)) {
40        lruMap.delete(key);
41    }
42
43    // Insert the key with its new value at the correct position in the access order
44    lruMap.set(key, value);
45
46    // If the cache size exceeds capacity, evict the LRU item from the cache
47    if (lruMap.size > lruCapacity) {
48        // The first key in the map is the least recently used key
49        const lruKey = lruMap.keys().next().value;
50        lruMap.delete(lruKey);
51    }
52}
53
54// Example of using the functions. Replace this with actual usage as needed.
55// initializeLRUCache(2); // Initialize the cache with a capacity of 2
56// console.log(getFromLRUCache(2)); // Should log -1 (not found)
57// putIntoLRUCache(2, 6); // Store the value 6 with key 2
58// console.log(getFromLRUCache(2)); // Should log 6
59