# 172ms DoubleLinkedList nodes and HashMap O(1)

• The idea is based on this.
We have double linked list for both node and frequency Node. Every frequency node has a double linkedlist node.

For example, capacity, (1, 1) has frequency 1, (2, 2) and (3, 3) has frequency 3.

FNode(-1) <-> FNode(1) <-> FNode(2) <-> FNode(-1) // FNode(-1) are dummy frequency nodes for head and tail.

• list item ******* ↕ ************** ↕

• list item Node(-1, -1) **** Node(-1, -1) //Node(-1,-1) are dummy nodes for head and tail.

• list item ******* ↕ ***************** ↕

• list item Node(1, 1)*******Node(2, 2)

• list item ******* ↕ ***************** ↕

• list item Node(-1. -1)*******Node(3, 3)

• list item *************************** ↕

• list item ********************* Node(-1, -1)

public class LFUCache {
class Node{
int key, value, frequency;
Node pre, next;
Node(int key, int value, int frequency) {
this.key = key;
this.value = value;
this.frequency = frequency;
pre = null;
next = null;
}
}
class FNode{ // Frequency Node
int frequency;
Node node, last = null;
FNode pre, next;
FNode(int frequency,Node node) {
this.frequency = frequency;
this.node = node;
pre = null;
next = null;
}
}
private int capacity;
private Map<Integer, Node> nodeMap;
private Map<Integer, FNode> frequencyMap;
private FNode fHead = new FNode(-1, new Node(-1, -1, -1)); //we have a dummy head, to make it easy to delete node
private FNode fTail = new FNode(-1, new Node(-1, -1, -1)); //we have a dummy tail, to make it easy to delete node
public LFUCache(int capacity) {
this.capacity = capacity;
nodeMap = new HashMap<>();
frequencyMap = new HashMap<>();
fHead.next = fTail;
fTail.pre = fHead;
}

``````public int get(int key) {
if (capacity < 1 || !nodeMap.containsKey(key)) {
return -1;
}
Node cur = nodeMap.get(key);
int originalFrequency = cur.frequency;
int frequency = originalFrequency + 1;
update(key, originalFrequency, frequency);
return cur.value;
}

public void set(int key, int value) {
if (capacity < 1) {
return;
}
int originalFrequency = 0;
int frequency = 1;
if (nodeMap.containsKey(key)) {
nodeMap.get(key).value = value; //updated node value
originalFrequency = nodeMap.get(key).frequency; // get the previous frequency
frequency = originalFrequency + 1;//  previous frequency plus 1
update(key, originalFrequency, frequency); //update node position in frequency node list
return;
} else if (nodeMap.size() == capacity) {
FNode smallFrequencyNode = fHead.next; //since it is from small to large, the first one after head is the least frequency.
Node tail = smallFrequencyNode.last;
int dKey = tail.pre.key;
deleteNode(tail.pre);//delete the least recently used node
nodeMap.remove(dKey);//remove from node map

if (smallFrequencyNode.node.next == smallFrequencyNode.last) {// means there is no node in this frequency node, we need delete it
deleteFNode(smallFrequencyNode);
frequencyMap.remove(smallFrequencyNode.frequency);
}
}
Node newNode = new Node(key, value, frequency);// otherwise it is a new node need to be added
nodeMap.put(key, newNode);
update(key, originalFrequency, frequency);

}

private void update(int key, int originalFrequency, int frequency) {
nodeMap.get(key).frequency = frequency;// update frequency
Node curNode = nodeMap.get(key);
if (curNode.next != null) { //means if this node is already exist in frequencynode, we need move it out from that frequencynode
deleteNode(curNode);
}
FNode FPresNode = frequencyMap.get(originalFrequency);
if (!frequencyMap.containsKey(frequency)) { // we find this is a new frequency, so we need create a new node
Node first = new Node(-1, -1, -1); //for each Node list, we also add dummy head and tail node
Node last = new Node(-1, -1, -1);
first.next = last;
last.pre = first;
moveToHead(curNode, first);// we move recently node to head.next

FNode fNewNode = new FNode(frequency, first);
fNewNode.last = last;// record last node in node list
if(FPresNode == null) FPresNode = fHead;
FPresNode.next.pre = fNewNode; //insert this new frequency node to frequency node list
fNewNode.next = FPresNode.next;
FPresNode.next = fNewNode;
fNewNode.pre = FPresNode;
frequencyMap.put(frequency, fNewNode);

} else {
FNode f = frequencyMap.get(frequency);
moveToHead(curNode, f.node);
}
if (FPresNode != null && FPresNode != fHead && FPresNode.node.next == FPresNode.last) {// which means no node in this frequency, we need to remove this frequency node from frequency node list
deleteFNode(FPresNode);
frequencyMap.remove(originalFrequency);
}
}

private void moveToHead(Node curNode, Node head) {// move the recently used node to head. since we have default head, so it actually move to head.next
curNode.next = head.next;
head.next.pre = curNode;
head.next = curNode;
curNode.pre = head;
}
private void deleteNode(Node node) { //delete node
node.next.pre = node.pre;
node.pre.next = node.next;
node.next = null;
node.pre = null;
}
private void deleteFNode(FNode node) { //delete frequency node
node.next.pre = node.pre;
node.pre.next = node.next;
}
``````

}

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