# [leetcode] LRU Cache

### 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.

tag: data structure

10/8/2015 update

Use a hash map and linked list to implement an algorithm with O(1) time complexity in both set() and get().

With a hash map, get is o(1) and set is o(1) is capacity is infinite.

With a linked list, set is o(1)(no duplicates) and get is o(n).

So we need to combine these two data structures.

hash map stores key-TreeNode pair

```class Node{
public:
int key;
int val;
Node * next, * prev;
Node(int k, int v):key(k), val(v), next(nullptr), prev(nullptr){}
};
class LRUCache{
public:
Node * head, * tail;//head is the most recently used node. Tail is the least recently used.
int size;
int capacity;
unordered_map<int, Node *> map;
LRUCache(int capacity) {
this->size = 0;
this->capacity = capacity;
map.clear();
}

int get(int key) {
Node * node;
if(map.find(key) == map.end()){
return -1;
}
else{
//find in cache
node = map[key];
if(size == 1 || node == head){
return node->val;
}
//size is more than 1, and node is not head

node->prev->next = node->next;
if(node == tail){
//move tail
tail = tail->prev;
tail->next = nullptr;
}
else{
node->next->prev = node->prev;
}
node->prev = nullptr;
}
}

void set(int key, int value) {
if(capacity == 0) return ;
if(map.find(key) != map.end()){
//found in list
map[key]->val = value;
get(key);
}
else{
Node * node = new Node(key, value);
map[key] = node;
if(size == 0){
}
else{
}
if(size == capacity){
//delete tail
map.erase(tail->key);
tail = tail->prev;
delete tail->next;
tail->next = nullptr;
}
else{
size++;
}
}
}
};```

```class node{
public:
int key;
int val;
int n;
node(int k, int v, int n): key(k), val(v), n(n) {}
};
class LRUCache{
public:
unsigned int count;//overflow bug
int size;
int capacity;
vector<node *> cache;
LRUCache(int capacity) {
this->capacity = capacity;
this->size = 0;
this->count = 0;
}

int get(int key) {//O(n)
vector<node*>::iterator it;
for(it = cache.begin(); it != cache.end(); it++){
if ((*it)->key == key){
(*it)->n = count++;
return (*it)->val;
}
}
return -1;
}

void set(int key, int value) {//O(n)
vector<node*>::iterator it;
vector<node*>::iterator minIt = cache.begin();
for(it = cache.begin(); it != cache.end(); it++){
if((*it)->key == key){
(*it)->val = value;
(*it)->n = count++;
return;
}
else{
if((*minIt)->n > (*it)->n){
minIt = it;
}
}
}
if(size < capacity){
node * p = new node(key, value, count++);
size++;
cache.push_back(p);
}
else{//full
(*minIt)->val = value;
(*minIt)->key = key;
(*minIt)->n = count++;
}
}
};```

```class node{
public:
int key;
int val;
node * next;
node * prev;
node(int k, int v): key(k), val(v), next(NULL), prev(NULL){}
};
class myList{
public:
int size;
node * tail;
void remove_tail(){
node * p = tail;
remove(p);
delete p;
}
node * get_tail(){
return tail;
}
void remove(node * p){
p->prev->next = p->next;
}
if(p != tail){
p->next->prev = p->prev;
}
}
}
if(p == tail){
tail = p->prev;
if(tail != NULL){
tail->next = NULL;
}
}
size--;
}
void push_front(node * p){
if(size == 0){
p->next = p->prev = NULL;
size++;
}
else{
p->prev = NULL;
size++;
}
}
};
class LRUCache{
public:
unordered_map <int, node *> hashMap;
myList* l = new myList();
int capacity;
LRUCache(int capacity) {
this->capacity = capacity;
}
int get(int key) {
if(hashMap.find(key) != hashMap.end()){//found
node * p = hashMap[key];
l->remove(p);
l->push_front(p);
return p->val;
}
return-1;
}
}

void set(int key, int value) {
if(get(key) != -1){//exist
hashMap[key]->val = value;
}
else{//not exist
node * p = new node(key, value);
if(l->size < capacity){//not full
l->push_front(p);
}
else{//full
int tailKey = l->get_tail()->key;
l->remove_tail();
hashMap.erase(tailKey);
l->push_front(p);
}
hashMap[key] = p;
}
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.