# Java O(n) Solution using one HashMap one Doubly Linked List

• ``````public class LFUCache {
class DLNode {
int key,val,freq;
DLNode pre,next;
DLNode(int key,int value) {
this.key = key;
this.val = value;
this.freq = 1;
}
}
class DLList {
DLList() {
tail = new DLNode(0,0);
}

public DLNode removeTheTail() {
DLNode node = tail.pre;
node.pre.next = tail;
tail.pre = node.pre;
return node;
}

public void remove(DLNode node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}

public void moveForward(DLNode node) {
DLNode cur = tail, next=cur;
next = cur;
cur = cur.pre;
}
next.pre = node;
node.next = next;
node.pre = cur;
cur.next = node;
}
}
int cap;
Map<Integer,DLNode> map;
DLList list;

public LFUCache(int capacity) {
this.cap = capacity;
this.map = new HashMap<Integer,DLNode>();
this.list = new DLList();
}

public int get(int key) {
if(!map.containsKey(key))
return -1;
DLNode node = map.get(key);
node.freq++;
list.remove(node);
list.moveForward(node);
return node.val;
}

public void put(int key, int value) {
if(cap==0)
return;
if(map.containsKey(key)) {
DLNode node = map.get(key);
node.val = value;
node.freq++;
list.remove(node);
list.moveForward(node);
return;
}
if(map.size()==cap) {
DLNode node = list.removeTheTail();
map.remove(node.key);
}
DLNode n = new DLNode(key,value);
list.moveForward(n);
map.put(key,n);
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.