{"id":900,"date":"2024-10-14T14:15:13","date_gmt":"2024-10-14T08:45:13","guid":{"rendered":"https:\/\/codexplained.in\/?p=900"},"modified":"2025-11-24T15:47:45","modified_gmt":"2025-11-24T10:17:45","slug":"implementation-of-lru-cache","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=900","title":{"rendered":"Implementation of LRU Cache"},"content":{"rendered":"\n

Key Concepts<\/h3>\n\n\n\n
    \n
  1. Cache Operations<\/strong>:\n
      \n
    • Get<\/strong>: Retrieve an item from the cache. If the item is present, it should be marked as recently used.<\/li>\n\n\n\n
    • Put<\/strong>: Add a new item to the cache. If the cache is full, remove the least recently used item.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
    • Data Structures<\/strong>:\n
        \n
      • A Doubly Linked List<\/strong> is used to keep track of the order of usage. The most recently used item will be at the front, and the least recently used item will be at the back.<\/li>\n\n\n\n
      • A Hash Map<\/strong> is used to store key-value pairs for quick access.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n

        Implementation Plan<\/h3>\n\n\n\n
          \n
        1. Node Structure<\/strong>: Create a structure for the nodes in the doubly linked list.<\/li>\n\n\n\n
        2. LRU Cache Class<\/strong>: Create a class that encapsulates the cache logic, using a hash map and a doubly linked list.<\/li>\n\n\n\n
        3. Functions<\/strong>:\n
            \n
          • get(key)<\/code>: Retrieve the value for a given key.<\/li>\n\n\n\n
          • put(key, value)<\/code>: Add a key-value pair to the cache.<\/li>\n\n\n\n
          • Helper functions to add and remove nodes from the linked list.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n

            C Program for LRU Cache<\/h3>\n\n\n
            \n#include <stdio.h>\n#include <stdlib.h>\n\ntypedef struct Node {\n    int key;\n    int value;\n    struct Node* prev;\n    struct Node* next;\n} Node;\n\ntypedef struct LRUCache {\n    int capacity;\n    Node* head; \/\/ Most recently used\n    Node* tail; \/\/ Least recently used\n    Node** map; \/\/ Hash map for fast access\n} LRUCache;\n\n\/\/ Create a new node\nNode* createNode(int key, int value) {\n    Node* newNode = (Node*)malloc(sizeof(Node));\n    newNode->key = key;\n    newNode->value = value;\n    newNode->prev = NULL;\n    newNode->next = NULL;\n    return newNode;\n}\n\n\/\/ Initialize the LRU Cache\nLRUCache* lruCreate(int capacity) {\n    LRUCache* cache = (LRUCache*)malloc(sizeof(LRUCache));\n    cache->capacity = capacity;\n    cache->head = NULL;\n    cache->tail = NULL;\n    cache->map = (Node**)calloc(capacity, sizeof(Node*));\n    return cache;\n}\n\n\/\/ Move a node to the head (most recently used)\nvoid moveToHead(LRUCache* cache, Node* node) {\n    if (cache->head == node) return; \/\/ Already at head\n\n    \/\/ Remove node from current position\n    if (node->prev) node->prev->next = node->next;\n    if (node->next) node->next->prev = node->prev;\n\n    \/\/ Update tail if needed\n    if (cache->tail == node) {\n        cache->tail = node->prev;\n        if (cache->tail) cache->tail->next = NULL;\n    }\n\n    \/\/ Move to head\n    node->next = cache->head;\n    node->prev = NULL;\n    if (cache->head) cache->head->prev = node;\n    cache->head = node;\n\n    \/\/ If tail is NULL, set it to head\n    if (!cache->tail) {\n        cache->tail = node;\n    }\n}\n\n\/\/ Remove the tail (least recently used)\nNode* removeTail(LRUCache* cache) {\n    if (!cache->tail) return NULL;\n    Node* node = cache->tail;\n    if (cache->tail->prev) {\n        cache->tail = cache->tail->prev;\n        cache->tail->next = NULL;\n    } else {\n        cache->head = NULL;\n        cache->tail = NULL;\n    }\n    return node;\n}\n\n\/\/ Get value from the cache\nint lruGet(LRUCache* cache, int key) {\n    int index = key % cache->capacity; \/\/ Simple hash function\n    Node* node = cache->map[index];\n\n    if (!node) return -1; \/\/ Not found\n\n    \/\/ Move accessed node to head\n    moveToHead(cache, node);\n    return node->value;\n}\n\n\/\/ Put a value into the cache\nvoid lruPut(LRUCache* cache, int key, int value) {\n    int index = key % cache->capacity;\n    Node* node = cache->map[index];\n\n    if (node) {\n        \/\/ Key exists, update the value and move to head\n        node->value = value;\n        moveToHead(cache, node);\n    } else {\n        \/\/ Key doesn't exist\n        Node* newNode = createNode(key, value);\n        if (cache->head == NULL) {\n            cache->head = newNode;\n            cache->tail = newNode;\n        } else {\n            moveToHead(cache, newNode);\n        }\n\n        cache->map[index] = newNode; \/\/ Add to hash map\n\n        \/\/ Check capacity\n        if (!cache->map[index]) {\n            Node* removed = removeTail(cache);\n            if (removed) {\n                cache->map[removed->key % cache->capacity] = NULL;\n                free(removed);\n            }\n        }\n    }\n}\n\n\/\/ Free the cache\nvoid lruFree(LRUCache* cache) {\n    Node* current = cache->head;\n    while (current) {\n        Node* next = current->next;\n        free(current);\n        current = next;\n    }\n    free(cache->map);\n    free(cache);\n}\n\n\/\/ Main function to test LRU Cache\nint main() {\n    LRUCache* cache = lruCreate(3); \/\/ Create LRU cache with capacity 3\n\n    lruPut(cache, 1, 1); \/\/ Cache is {1=1}\n    lruPut(cache, 2, 2); \/\/ Cache is {1=1, 2=2}\n    printf("Get 1: %d\\n", lruGet(cache, 1)); \/\/ Returns 1, Cache is {2=2, 1=1}\n    lruPut(cache, 3, 3); \/\/ Cache is {2=2, 1=1, 3=3}\n    lruPut(cache, 4, 4); \/\/ Evicts key 2, Cache is {1=1, 3=3, 4=4}\n    printf("Get 2: %d\\n", lruGet(cache, 2)); \/\/ Returns -1 (not found)\n    lruPut(cache, 5, 5); \/\/ Evicts key 1, Cache is {3=3, 4=4, 5=5}\n\n    printf("Get 1: %d\\n", lruGet(cache, 1)); \/\/ Returns -1 (not found)\n    printf("Get 3: %d\\n", lruGet(cache, 3)); \/\/ Returns 3\n    printf("Get 4: %d\\n", lruGet(cache, 4)); \/\/ Returns 4\n    printf("Get 5: %d\\n", lruGet(cache, 5)); \/\/ Returns 5\n\n    lruFree(cache); \/\/ Clean up the cache\n    return 0;\n}\n\n<\/pre><\/div>\n\n\n
            Explanation of the Code<\/h3>\n\n\n\n
              \n
            1. Node Structure<\/strong>: Each node contains a key-value pair along with pointers to the previous and next nodes, allowing for efficient insertion and deletion in a doubly linked list.<\/li>\n\n\n\n
            2. Cache Structure<\/strong>: The LRUCache<\/code> struct contains the capacity, pointers to the head and tail of the doubly linked list, and an array of pointers (map<\/code>) for fast access.<\/li>\n\n\n\n
            3. Basic Operations<\/strong>:\n
                \n
              • Creating a Node<\/strong>: The createNode<\/code> function initializes a new node.<\/li>\n\n\n\n
              • Cache Initialization<\/strong>: The lruCreate<\/code> function initializes the cache structure.<\/li>\n\n\n\n
              • Move to Head<\/strong>: The moveToHead<\/code> function rearranges the linked list to mark a node as recently used.<\/li>\n\n\n\n
              • Remove Tail<\/strong>: The removeTail<\/code> function evicts the least recently used node from the cache.<\/li>\n\n\n\n
              • Get Operation<\/strong>: The lruGet<\/code> function retrieves a value and updates the usage order.<\/li>\n\n\n\n
              • Put Operation<\/strong>: The lruPut<\/code> function adds or updates an entry in the cache, evicting the least recently used entry if needed.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
              • Memory Management<\/strong>: The lruFree<\/code> function deallocates memory used by the cache.<\/li>\n\n\n\n
              • Main Function<\/strong>: Demonstrates how to use the cache by adding and retrieving items.<\/li>\n<\/ol>\n\n\n\n
                Input and Output Example<\/h3>\n\n\n\n
                Input<\/h4>\n\n\n\n
                The operations performed in the main function can be considered the input to the cache:<\/p>\n\n\n\n
                 codelruPut(cache, 1, 1); \/\/ Cache is {1=1}
                lruPut(cache, 2, 2); \/\/ Cache is {1=1, 2=2}
                printf(\"Get 1: %d\\n\", lruGet(cache, 1)); \/\/ Returns 1
                lruPut(cache, 3, 3); \/\/ Cache is {1=1, 2=2, 3=3}
                lruPut(cache, 4, 4); \/\/ Evicts key 2
                printf(\"Get 2: %d\\n\", lruGet(cache, 2)); \/\/ Returns -1
                <\/code><\/pre>\n\n\n\n
                Output<\/h4>\n\n\n\n
                codeGet 1: 1
                Get 2: -1
                Get 1: -1
                Get 3: 3
                Get 4: 4
                Get 5: 5
                <\/code><\/pre>\n\n\n\n
                Explanation of the Output<\/h3>\n\n\n\n
                The output shows the results of the get<\/code> operations, demonstrating that when an item is accessed, it moves to the front of the cache, and when the cache exceeds its capacity, the least recently used item is removed.<\/p>\n\n\n\n
                This code should compile and run without issues, providing a working implementation of an LRU Cache. If you have further requirements or modifications, feel free to ask!<\/p>\n\n\n\n
                <\/p>\n