Key Concepts
- Cache Operations:
- Get: Retrieve an item from the cache. If the item is present, it should be marked as recently used.
- Put: Add a new item to the cache. If the cache is full, remove the least recently used item.
- Data Structures:
- A Doubly Linked List 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.
- A Hash Map is used to store key-value pairs for quick access.
Implementation Plan
- Node Structure: Create a structure for the nodes in the doubly linked list.
- LRU Cache Class: Create a class that encapsulates the cache logic, using a hash map and a doubly linked list.
- Functions:
get(key): Retrieve the value for a given key.put(key, value): Add a key-value pair to the cache.- Helper functions to add and remove nodes from the linked list.
C Program for LRU Cache
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int key;
int value;
struct Node* prev;
struct Node* next;
} Node;
typedef struct LRUCache {
int capacity;
Node* head; // Most recently used
Node* tail; // Least recently used
Node** map; // Hash map for fast access
} LRUCache;
// Create a new node
Node* createNode(int key, int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->key = key;
newNode->value = value;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
// Initialize the LRU Cache
LRUCache* lruCreate(int capacity) {
LRUCache* cache = (LRUCache*)malloc(sizeof(LRUCache));
cache->capacity = capacity;
cache->head = NULL;
cache->tail = NULL;
cache->map = (Node**)calloc(capacity, sizeof(Node*));
return cache;
}
// Move a node to the head (most recently used)
void moveToHead(LRUCache* cache, Node* node) {
if (cache->head == node) return; // Already at head
// Remove node from current position
if (node->prev) node->prev->next = node->next;
if (node->next) node->next->prev = node->prev;
// Update tail if needed
if (cache->tail == node) {
cache->tail = node->prev;
if (cache->tail) cache->tail->next = NULL;
}
// Move to head
node->next = cache->head;
node->prev = NULL;
if (cache->head) cache->head->prev = node;
cache->head = node;
// If tail is NULL, set it to head
if (!cache->tail) {
cache->tail = node;
}
}
// Remove the tail (least recently used)
Node* removeTail(LRUCache* cache) {
if (!cache->tail) return NULL;
Node* node = cache->tail;
if (cache->tail->prev) {
cache->tail = cache->tail->prev;
cache->tail->next = NULL;
} else {
cache->head = NULL;
cache->tail = NULL;
}
return node;
}
// Get value from the cache
int lruGet(LRUCache* cache, int key) {
int index = key % cache->capacity; // Simple hash function
Node* node = cache->map[index];
if (!node) return -1; // Not found
// Move accessed node to head
moveToHead(cache, node);
return node->value;
}
// Put a value into the cache
void lruPut(LRUCache* cache, int key, int value) {
int index = key % cache->capacity;
Node* node = cache->map[index];
if (node) {
// Key exists, update the value and move to head
node->value = value;
moveToHead(cache, node);
} else {
// Key doesn't exist
Node* newNode = createNode(key, value);
if (cache->head == NULL) {
cache->head = newNode;
cache->tail = newNode;
} else {
moveToHead(cache, newNode);
}
cache->map[index] = newNode; // Add to hash map
// Check capacity
if (!cache->map[index]) {
Node* removed = removeTail(cache);
if (removed) {
cache->map[removed->key % cache->capacity] = NULL;
free(removed);
}
}
}
}
// Free the cache
void lruFree(LRUCache* cache) {
Node* current = cache->head;
while (current) {
Node* next = current->next;
free(current);
current = next;
}
free(cache->map);
free(cache);
}
// Main function to test LRU Cache
int main() {
LRUCache* cache = lruCreate(3); // Create LRU cache with capacity 3
lruPut(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, Cache is {2=2, 1=1}
lruPut(cache, 3, 3); // Cache is {2=2, 1=1, 3=3}
lruPut(cache, 4, 4); // Evicts key 2, Cache is {1=1, 3=3, 4=4}
printf("Get 2: %d\n", lruGet(cache, 2)); // Returns -1 (not found)
lruPut(cache, 5, 5); // Evicts key 1, Cache is {3=3, 4=4, 5=5}
printf("Get 1: %d\n", lruGet(cache, 1)); // Returns -1 (not found)
printf("Get 3: %d\n", lruGet(cache, 3)); // Returns 3
printf("Get 4: %d\n", lruGet(cache, 4)); // Returns 4
printf("Get 5: %d\n", lruGet(cache, 5)); // Returns 5
lruFree(cache); // Clean up the cache
return 0;
}
Explanation of the Code
- Node Structure: 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.
- Cache Structure: The
LRUCachestruct contains the capacity, pointers to the head and tail of the doubly linked list, and an array of pointers (map) for fast access. - Basic Operations:
- Creating a Node: The
createNodefunction initializes a new node. - Cache Initialization: The
lruCreatefunction initializes the cache structure. - Move to Head: The
moveToHeadfunction rearranges the linked list to mark a node as recently used. - Remove Tail: The
removeTailfunction evicts the least recently used node from the cache. - Get Operation: The
lruGetfunction retrieves a value and updates the usage order. - Put Operation: The
lruPutfunction adds or updates an entry in the cache, evicting the least recently used entry if needed.
- Creating a Node: The
- Memory Management: The
lruFreefunction deallocates memory used by the cache. - Main Function: Demonstrates how to use the cache by adding and retrieving items.
Input and Output Example
Input
The operations performed in the main function can be considered the input to the cache:
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
Output
codeGet 1: 1
Get 2: -1
Get 1: -1
Get 3: 3
Get 4: 4
Get 5: 5
Explanation of the Output
The output shows the results of the get 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.
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!
