Design a data structure that allows O(1) time complexity to insert, delete and get most frequent element.
At first, a hash map seems to be good for insertion and deletion. But how to make getMostFrequent O(1)? Regular sorting algorithm takes nlogn, so we can not use that. As a result we can use a linked list to track the maximum frequency.
In the implementation above, we only add nodes to the list. We can also delete nodes that does not hold any elements.