# Java easy understanding solution using HashMap and DoublyLinkedList

• Similar but more concise than the top solution. I just swap nodes if current node's count >= next node's count when increase count, in this way, nodes with larger frequency and most recently used can bo moved to the back of doubly linked list.

public class LFUCache {

``````private class Node {
Node prev;
Node next;
int value;
int key;
public Node(int key, int value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}

private HashMap<Integer, Node> map;
private HashMap<Integer, Integer> valueMap;  //used to keep track of count
private int capacity;
private Node head = new Node(-1, -1); //dummy
private Node tail = new Node(-1, -1);

public LFUCache(int capacity) {
this.map = new HashMap<Integer, Node>();
this.valueMap = new HashMap<Integer, Integer>();
this.capacity = capacity;
valueMap.put(-1, Integer.MAX_VALUE);
}

public int get(int key) {
if (map.containsKey(key)) {
increaseCount(key);
return map.get(key).value;
}
return -1;
}

public void put(int key, int value) {
if (capacity == 0 ) return;
if (map.containsKey(key)) {
map.get(key).value = value;
increaseCount(key);
} else {
if (map.size() == capacity) {
}
Node newNode = new Node(key, value);
map.put(key, newNode);
valueMap.put(key, 1);
}

}

newNode.next = tmp;
tmp.prev = newNode;
while(newNode != tail && valueMap.get(newNode.next.key) <= valueMap.get(newNode.key)) {
swap(newNode);
}
}

private void increaseCount(int key) {
Node node = map.get(key);
valueMap.put(key, valueMap.get(node.key) + 1);
while(node != tail && valueMap.get(node.next.key) <= valueMap.get(key)) {
swap(node);
}
}

private void swap(Node current) {
Node tmp = current.next;
Node p = current.prev;
Node n = tmp.next;

p.next = tmp;
tmp.prev = p;
current.prev = tmp;
tmp.next = current;
current.next = n;
n.prev = current;
}
``````

}

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