# Design LRU cache

### 20 January, 2014 - 7 min read

You have to design a LRU cache such that all operations can be done in O(1) – read, write and insert.

- In case, cache is full, you have to remove an element which was read/written last.
- Each read should update the timestamp of these elements.
- Read request of the element contains a key which is not the location of the element.

**Strategy:**

Assuming hashmap has retrieval complexity of O(1), we can do this using a doubly link list and a Hashmap

- Doubly link list will be used to store indexes sorted by date/timestamp information.
- Keep track of first and last node.
- No sorting effort is needed as each new node will have latest timestamp.
- The Hashmap will retrieve the node searched by key. It will also contain pointer to its respective doubly link list node.

READ -

- Search the node by key. Retrieve the node value and index for doubly linklist.
- Delete the node from doubly linked list and add it with the updated date value at the starting of the list.
- Complexity of deleting a node in doubly link list is O(1) as we can reach to it without traversing the list.

INSERT -

- Add the new node in the hashmap and the doubly linked list.
- If the cache is full, use the pointer to the last node in the doubly linked list and delete that node. Set the delete pointer appropriately.
- Inserting at the start of linked list is operation with time O(1).

UPDATE -

- Update operation will need similar operation as READ in terms of accessing the data structure. Hence, similar time complexities apply.

DELETE -

- Deleting the node from the doubly-linked list and hashmap can be done in O(1).

Implementation:

Queue with DLL + HashMap

1: struct LRUCacheNode {

2: int key;

3: int value;

` 4: LRUCacheNode* prev;`

` 5: LRUCacheNode* next;`

` 6: LRUCacheNode(): key(0),value(0),next(NULL),prev(NULL) { } ;`

` 7: } ;`

` 8:`

9: class LRUCache{

10: private:

11: hash_map< int, LRUCacheNode* > Map;

` 12: LRUCacheNode * Head;`

` 13: LRUCacheNode * Tail;`

14: int Capacity ;

15: int Count ;

` 16:`

17: public:

18: LRUCache(int capacity) {

` 19: Capacity = capacity ;`

` 20: Count = 0 ;`

21: Head = new LRUCacheNode;

22: Tail = new LRUCacheNode;

` 23: Head->prev = NULL;`

` 24: Head->next = Tail;`

` 25: Tail->next = NULL;`

` 26: Tail->prev = Head;`

` 27: }`

` 28:`

` 29: ~LRUCache ( ) {`

30: delete Head;

31: delete Tail;

` 32: }`

` 33:`

34: int get(int key) {

` 35: LRUCacheNode* node = Map[key];`

36: if(node)

` 37: {`

` 38: DetachNode(node);`

` 39: AttachNodeToFront(node);`

40: return node->value;

` 41: }`

42: else

43: return -1 ;

` 44:`

` 45: }`

` 46:`

47: void set(int key, int value) {

` 48: LRUCacheNode* node = Map[key];`

49: if(node)

` 50: {`

` 51: DetachNode(node);`

` 52: node->value = value;`

` 53: AttachNodeToFront(node);`

` 54: }`

55: else{

56: LRUCacheNode* node = new LRUCacheNode ;

57: if ( Capacity == Count ) { // If Cache is Full

` 58: RemoveLRUNode ( key ) ;`

` 59: }`

` 60:`

` 61: node->key = key;`

` 62: node->value = value;`

` 63: Map[key] = node;`

` 64: AttachNodeToFront(node);`

` 65: Count++ ;`

` 66: }`

` 67: }`

68: private:

69: void RemoveLRUNode ( int key ) {

` 70: LRUCacheNode* node = Tail->prev;`

` 71: DetachNode(node);`

` 72: Map.erase(node->key);`

` 73: Count-- ;`

` 74: }`

` 75:`

76: void DetachNode(LRUCacheNode* node) {

` 77: node->prev->next = node->next;`

` 78: node->next->prev = node->prev;`

` 79: }`

` 80:`

81: void AttachNodeToFront(LRUCacheNode* node) {

` 82: node->next = Head->next;`

` 83: node->prev = Head;`

` 84: Head->next = node;`

` 85: node->next->prev = node;`

` 86: }`

` 87: };`