# Share My clear solution, easy to understand.

• ``````struct NodeVal{
NodeVal *pre, *next;
int val, key;
NodeVal(int v, int k):val(v), key(k), pre(NULL), next(NULL){}
};

struct NodeFreq{
NodeVal *front, *back;
NodeFreq *pre, *next;
int freq;
NodeFreq(int f):freq(f){
front = new NodeVal(-1, -1);
back = new NodeVal(-1, -1);
front -> next = back;
back -> pre = front;
}
};

class LFUCache {
public:
unordered_map<int, pair<NodeVal*, NodeFreq*>> imv;
NodeFreq *front, *back;
int size, capacity;
LFUCache(int capacity) {
this -> capacity = capacity;
this -> size = 0;
front = new NodeFreq(-1);
back = new NodeFreq(-1);
front -> next = back;
back -> pre = front;
}

void delVal(NodeVal *nv){
nv -> pre -> next = nv -> next;
nv -> next -> pre = nv -> pre;
free(nv);
}

void delFreq(NodeFreq *nf){
nf -> pre -> next = nf -> next;
nf -> next -> pre = nf -> pre;
free(nf);
}

NodeFreq *node = new NodeFreq(freq);
node -> next = nf -> next;
node -> pre = nf;
nf -> next = node;
node -> next -> pre = node;

return node;
}

NodeVal* addVal(NodeVal *nv, int val, int key){
NodeVal *node = new NodeVal(val, key);
node -> next = nv -> next;
node -> pre = nv;
nv -> next = node;
node -> next -> pre = node;

return node;
}

int get(int key) {
if(imv.count(key) == 0) return -1;

NodeVal *nv = imv[key].first;
NodeFreq *nf = imv[key].second;

if(nf -> next -> freq != nf -> freq + 1){
addFreq(nf, nf -> freq + 1);
}
NodeFreq *nnf = nf -> next;
NodeVal *nnv = addVal(nnf -> front, nv -> val, nv -> key);
delVal(nv);
if(nf -> front -> next == nf -> back)
delFreq(nf);

imv[key].first = nnv;
imv[key].second = nnf;

return nnv -> val;
}

void put(int key, int value) {
if(capacity <= 0) return;

if(imv.count(key) != 0){
NodeVal *nv = imv[key].first;
NodeFreq *nf = imv[key].second;

if(nf -> next -> freq != nf -> freq + 1){
addFreq(nf, nf -> freq + 1);
}
NodeFreq *nnf = nf -> next;
NodeVal *nnv = addVal(nnf -> front, value, key);
delVal(nv);
if(nf -> front -> next == nf -> back)
delFreq(nf);

imv[key].first = nnv;
imv[key].second = nnf;

return ;
}

NodeFreq *dnf = this -> front -> next;

if(size == capacity){
NodeVal *dnv = dnf -> back -> pre;
imv.erase(dnv -> key);
delVal(dnv);
size --;
if(dnf -> front -> next == dnf -> back)
delFreq(dnf);
}
dnf = this -> front -> next;
if(dnf -> freq != 0)