## LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations:

`get`

and `set`

.`get(key)`

- Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.`set(key, value)`

- Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.### Analysis:

This a more likely a design question other than a algorithm question, which requires us to choose the proper data structure and implement the "get", "set" methods.

At the first glance, a queue seems enough for this problem, because of its FIFO property. However, the questions also requires "Recently", which means both "input" and "visit" are "recent actions" for the data. If you have the data "<1,1>" the least recently used element in the queue <1,1> <2,2><3,3>, if method "get(1)" is called, "<1,1>" is now becoming the last (recently used) element in the queue. (<2,2,><3,3,><1,1>)

Consider the basic operations we need:

(1) Insert a new <key, value> pair to the end of the list.

(2) delete a <key, value> pair (if the cache is full).

(3) move a <key, value> pair to the end. (when it is used)

(3) change the value in a <key, value> pair and move it to the end.

Therefore, a double linked list can handle the above methods well. A map<key, node*> is a good way tracking the position of the node according to its key.

Be careful with the following cases:

(1) List is empty

(2) List has one node

(3) Initialization

(4) Don't forget delete the element in the map when it is removed from list.

### Code:

class LRUCache{ //define the double linked list, each node stores both the key and value. struct Node{ Node* next; Node* prev; int value; int key; Node(Node* p, Node* n, int k, int val):prev(p),next(n),key(k),value(val){}; Node(int k, int val):prev(NULL),next(NULL),key(k),value(val){}; }; map<int,Node*>mp; //map the key to the node in the linked list int cp; //capacity Node* tail; // double linked list tail pointer Node* head; // double linked list head pointer public: //constructor LRUCache(int capacity) { cp = capacity; mp.clear(); head=NULL; tail=NULL; } //insert node to the tail of the linked list void insertNode(Node* node){ if (!head){ head = node; tail = node; }else{ tail->next = node; node->prev = tail; tail = tail->next; } } //remove current node void rmNode(Node* node){ if (node==head){ head = head->next; if (head){head->prev = NULL;} }else{ if (node==tail){ tail =tail->prev; tail->next = NULL; }else{ node->next->prev = node->prev; node->prev->next = node->next; } } } // move current node to the tail of the linked list void moveNode(Node* node){ if (tail==node){ return; }else{ if (node==head){ node->next->prev = NULL; head = node->next; tail->next = node; node->prev = tail; tail=tail->next; }else{ node->prev->next = node->next; node->next->prev = node->prev; tail->next = node; node->prev = tail; tail=tail->next; } } } /////////////////////////////////////////////////////////////////////// // get method /////////////////////////////////////////////////////////////////////// int get(int key) { if (mp.find(key)==mp.end()){ return -1; }else{ Node *tmp = mp[key]; moveNode(tmp); return mp[key]->value; } } /////////////////////////////////////////////////////////////////////// // set method /////////////////////////////////////////////////////////////////////// void set(int key, int value) { if (mp.find(key)!=mp.end()){ moveNode(mp[key]); mp[key]->value = value; }else{ if (mp.size()==cp){ mp.erase(head->key); rmNode(head); } Node * node = new Node(key,value); mp[key] = node; insertNode(node); } } };

Hello Yu! I am just wondering if tail should also be dealt with in line 44-46. If there is only one node in the list, which is head==tail, after we remove it(head), we should set tail = NULL. Please correct me if I am wrong with it.

ReplyDeleteDo you need to remove space since you Node * node = new Node(key,value);

ReplyDeletebut no deletion?

+1. And if the capacity==0, the program will crash if set operation is called.

DeleteThis comment has been removed by the author.

ReplyDelete