An LRU (Least Recently Used) cache is a data structure that stores a fixed number of elements. When the cache reaches its limit, it evicts the least recently used item to make space for a new one. The LRU cache is commonly used in memory management systems to keep frequently accessed data in memory while discarding less-used data.
Program Explanation
This LRU Cache is implemented using two main data structures:
- A doubly linked list that stores the elements in the order of use. The most recently used elements are near the front, and the least recently used elements are near the end.
- A hash map (array in this case) that stores pointers to the nodes of the doubly linked list, allowing for fast access, insertions, and deletions.
C Program Code
#include <stdio.h>
#include <stdlib.h>
#define CACHE_CAPACITY 3 // Define the capacity of the LRU cache
// Node of the doubly linked list
struct Node {
int key;
int value;
struct Node *prev, *next;
};
// Doubly linked list to represent LRU Cache
struct DoublyLinkedList {
struct Node *head, *tail;
int size;
};
// Hash map to store pointers to nodes (direct access)
struct Node* hashMap[CACHE_CAPACITY];
// Initialize the doubly linked list (LRU Cache)
void initList(struct DoublyLinkedList *list) {
list->head = list->tail = NULL;
list->size = 0;
}
// Create a new node for the linked list
struct Node* createNode(int key, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->key = key;
newNode->value = value;
newNode->prev = newNode->next = NULL;
return newNode;
}
// Add a node to the front of the list (Most Recently Used)
void addToFront(struct DoublyLinkedList *list, struct Node* node) {
node->next = list->head;
node->prev = NULL;
if (list->head != NULL)
list->head->prev = node;
list->head = node;
if (list->tail == NULL) // First node is both head and tail
list->tail = node;
list->size++;
}
// Remove a node from the list (from any position)
void removeNode(struct DoublyLinkedList *list, struct Node* node) {
if (node->prev != NULL)
node->prev->next = node->next;
else
list->head = node->next;
if (node->next != NULL)
node->next->prev = node->prev;
else
list->tail = node->prev;
list->size--;
free(node);
}
// Move a node to the front (Most Recently Used)
void moveToFront(struct DoublyLinkedList *list, struct Node* node) {
if (list->head == node) return; // Node is already at the front
// Remove node from current position and add to front
removeNode(list, node);
addToFront(list, node);
}
// Remove the Least Recently Used node (from the end)
void removeLRU(struct DoublyLinkedList *list) {
if (list->tail != NULL) {
hashMap[list->tail->key] = NULL; // Remove from hash map
removeNode(list, list->tail);
}
}
// LRU Cache structure with a doubly linked list and hash map
struct LRUCache {
struct DoublyLinkedList list;
int capacity;
};
// Initialize the LRU cache
void initCache(struct LRUCache *cache, int capacity) {
cache->capacity = capacity;
initList(&cache->list);
for (int i = 0; i < CACHE_CAPACITY; i++) { hashMap[i] = NULL; } } // Get the value of a key from the cache int get(struct LRUCache *cache, int key) { if (hashMap[key] == NULL) { printf("Key %d not found in cache.\n", key); return -1; // Key not found } struct Node *node = hashMap[key]; moveToFront(&cache->list, node); // Mark as Most Recently Used
printf("Key %d found in cache with value %d\n", key, node->value);
return node->value;
}
// Put a key-value pair into the cache
void put(struct LRUCache *cache, int key, int value) {
if (hashMap[key] != NULL) {
// Key already exists, update the value and move to front
struct Node *node = hashMap[key];
node->value = value;
moveToFront(&cache->list, node);
printf("Updated key %d in cache with new value %d\n", key, value);
} else {
// New key, check if cache is full
if (cache->list.size == cache->capacity) {
printf("Cache is full, removing least recently used key %d\n", cache->list.tail->key);
removeLRU(&cache->list);
}
// Insert new key-value pair
struct Node *newNode = createNode(key, value);
addToFront(&cache->list, newNode);
hashMap[key] = newNode;
printf("Inserted key %d with value %d into cache\n", key, value);
}
}
// Main function to demonstrate LRU cache
int main() {
struct LRUCache cache;
initCache(&cache, CACHE_CAPACITY);
// Cache operations
put(&cache, 1, 10); // Insert key 1 with value 10
put(&cache, 2, 20); // Insert key 2 with value 20
put(&cache, 3, 30); // Insert key 3 with value 30
get(&cache, 1); // Access key 1 (Most Recently Used)
put(&cache, 4, 40); // Insert key 4 (causes LRU eviction of key 2)
get(&cache, 2); // Try to access key 2 (should be evicted)
get(&cache, 3); // Access key 3
return 0;
}
Code Explanation
1. Data Structures:
Node: Represents a node in the doubly linked list. Each node stores a key-value pair and pointers to the previous and next node in the list.DoublyLinkedList: Manages the doubly linked list. This structure contains pointers to the head and tail of the list and tracks the size of the cache.hashMap: This array allows direct access to nodes in constant time. Each entry in the array points to a node in the linked list, which holds the actual key-value pair.
2. LRU Cache Operations:
put(): Adds a key-value pair to the cache. If the key already exists, the value is updated, and the key is moved to the front (Most Recently Used). If the cache is full, the Least Recently Used (LRU) key is evicted before inserting the new key.get(): Retrieves the value associated with a key. If the key is found, it is moved to the front (Most Recently Used). If not, the function returns-1to indicate that the key is not in the cache.moveToFront(): Moves a node to the front of the linked list to mark it as Most Recently Used.removeLRU(): Removes the least recently used node (at the tail of the list).
Sample Output
Inserted key 1 with value 10 into cache
Inserted key 2 with value 20 into cache
Inserted key 3 with value 30 into cache
Key 1 found in cache with value 10
Cache is full, removing least recently used key 2
Inserted key 4 with value 40 into cache
Key 2 not found in cache.
Key 3 found in cache with value 30
Conclusion
This C program implements an LRU cache using a doubly linked list and a hash map. The hash map allows for fast access, and the doubly linked list ensures that we can efficiently remove and insert elements in O(1) time. This design is widely used in memory management and caching mechanisms where quick access and eviction policies are crucial.
