Hi,
I am a bit confused about the solution for the LFU (and LRU) in the netflix category.
How is deleting a random node in a linked list O(1) ?
LinkedListNode Get(int key) {
if(!keyDict.containsKey(key)){
return null;
}
LinkedListNode temp = this.keyDict.get(key);
**this.freqDict.get(temp.freq).remove(temp);**
if(this.freqDict.get(this.keyDict.get(key).freq) == null){
this.freqDict.remove(this.keyDict.get(key).freq);
if(this.minFreq == this.keyDict.get(key).freq){
this.minFreq += 1;
}
}
this.keyDict.get(key).freq += 1;
if(!this.freqDict.containsKey(this.keyDict.get(key).freq)){
this.freqDict.put(this.keyDict.get(key).freq, new LinkedList<LinkedListNode>());
}
this.freqDict.get(this.keyDict.get(key).freq).addLast(this.keyDict.get(key));
return this.keyDict.get(key);
}
the java 8 source implementation is :
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
**for (Node<E> x = first; x != null; x = x.next) {**
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
Am i missing something?