<p class="wp-block-paragraph">In this article, we will discuss how to create a Data Structure with Insert, Delete and GetMostFrequent operations of O(1). This Data Structure will proform Insert, delete, and get the most frequent item in the constant time.</p>



<p class="wp-block-paragraph">As we know that the insertion and deletion will be performed on a hash map with the constant time O(1). So, a hash map will be the right choice for insertion and deletion. But, how to implement get most frequent method with O(1) time.</p>



<div class="wp-block-image"><figure class="aligncenter"><img src="https://i0.wp.com/dineshonjava.com/wp-content/uploads/2019/10/Get-Most-Frequent-Data-Structure.jpeg?fit=530%2C398&;ssl=1" class="wp-image-4496"/><figcaption><strong>Creating Data Structure with Insert, Delete and GetMostFrequent of O(1)</strong></figcaption></figure></div>



<p class="wp-block-paragraph">Let&#8217;s see the following implementation of this method to achieve get the most frequent item with O(1) time.</p>



<blockquote class="wp-block-quote is-layout-flow wp-block-quote-is-layout-flow"><p>Other Data Structures Articles</p><cite>1. <a href="https://dineshonjava.com/implement-lru-cache-algorithm-in-java/"><strong>Create a LRU cache</strong></a><br>2. <a href="https://dineshonjava.com/least-frequently-used-lfu-cache-implementation/"><strong>Create a LFU cache</strong></a></cite></blockquote>



<h2 class="wp-block-heading">Create a Data Structure with Insert, Delete and GetMostFrequent of O(1)</h2>



<p class="wp-block-paragraph">We will get the solution for this problem by using HashMap and LinkedList. Let&#8217; see the following code:</p>



<pre class="wp-block-code"><code>/**
 * 
 */
package com.dineshonjava.algo.gmf;

import java.util.HashSet;
import java.util.Set;

/**
 * @author Dinesh.Rajput
 *
 */
public class Node {
	
	int value;
	Node prev;
	Node next;
	Set<;Integer> set;
 
	public Node(int v){
		value = v;
		set = new HashSet<;Integer>();
	}
}
</code></pre>



<p class="wp-block-paragraph">We will use the <em>LinkedList </em>to hold the frequency of the item in the data structure along with the item stored in the <em>HashSet</em>. This set will contain all items with the same frequency. Let&#8217;s see the other class of our Data structure.</p>



<pre class="wp-block-code"><code>/**
 * 
 */
package com.dineshonjava.algo.gmf;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Dinesh.Rajput
 *
 */
public class GetMostFrequent {
	
	Map<;Integer, Node> map;
	Node tail, head;
	
	/** Initialize your data structure here. */
	public GetMostFrequent() {
		super();
		map = new HashMap<;>();
	}
	
	/** Adding items to your data structure. */
	public void add(int val) {
		
		if(map.containsKey(val)) {
			Node node = map.get(val);
			node.set.remove(val);
			if(node.next != null) {
				node.next.set.add(val);
				map.put(val, node.next);
			}else {
				Node newnode = new Node(node.value+1);
				newnode.set.add(val);
				map.put(val, newnode);
				node.next = newnode;
				newnode.prev = node;
				tail = newnode;
			}
		}else {
			if(head != null &;&; tail != null) {
				if(tail.value > 1) {
					head.set.add(val);
					map.put(val, head);
				}else {
					tail.set.add(val);
					map.put(val, tail);
				}
			}else {
				Node node = new Node(1);
				node.set.add(val);
				map.put(val, node);
				head = node;
				tail = node;
			}
		}
	}
	
	/** Getting most frequent item from your data structure. */
	public int getMostFrequent() {
		
		if(tail == null)
			return -1;
		
		return tail.set.iterator().next();
	}
	
	/** Removing item from your data structure. */
	public void remove(int val) {
		
		if(map.containsKey(val)) {
			Node node = map.get(val);
			node.set.remove(val);
			
			if(node.value == 1){
				map.remove(val);
			}else{
				node.prev.set.add(val);
				map.put(val, node.prev);
			}
			
			while(tail != null &;&; tail.set.size() == 0){
				tail = tail.prev;
			}
			
		}else {
			System.out.println("No such item exist!!!");
		}
	}
}
</code></pre>



<p class="wp-block-paragraph">The above <em>GetMostFrequent </em>our collection data structure class, it has three methods <em>add()</em>, <em>remove()</em>, and <em>getMostFrequent(). All these methods have</em> time complexity of O(1).</p>



<p class="wp-block-paragraph">Let&#8217;s create a test class for this data structure as the following:</p>



<pre class="wp-block-code"><code>/**
 * 
 */
package com.dineshonjava.algo.gmf;

/**
 * @author Dinesh.Rajput
 *
 */
public class GMFTest {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		//Creating your data structure object
		GetMostFrequent frequent = new GetMostFrequent();
		
		//Adding items to your data structure with O(1)
		frequent.add(2);
		frequent.add(3);
		frequent.add(4);
		frequent.add(5);
		frequent.add(2);
		frequent.add(6);
		frequent.add(3);
		frequent.add(3);
		frequent.add(2);
		frequent.add(2);
		
		//Getting most frequent item from your data structure with O(1)
		System.out.println("Most frequent number in the collection is "+frequent.getMostFrequent()); //Expected 2
		
		//Removing item from your data structure with O(1)
		frequent.remove(2);
		frequent.remove(2);
		
		System.out.println("Most frequent number in the collection is "+frequent.getMostFrequent()); //Expected 3
		
	}

}
</code></pre>



<p class="wp-block-paragraph">Let&#8217;s run this test class and see the following output.</p>



<pre class="wp-block-code"><code>Most frequent number in the collection is 2
Most frequent number in the collection is 3</code></pre>



<p class="wp-block-paragraph"></p>
<div class="wp-post-navigation"> 
									 <div class="wp-post-navigation-pre"> 
									 <a href="https://dineshonjava.com/least-frequently-used-lfu-cache-implementation/">Previous</a> 
									 </div> 
									 <div class="wp-post-navigation-next"> 
									 
									 </div> 
									</div>
<script type="text/javascript">
jQuery(document).ready(function($) {
 $.post('https://dineshonjava.com/wp-admin/admin-ajax.php', {action: 'mts_view_count', id: '4495'});
});
</script>
Strategy Design Patterns We can easily create a strategy design pattern using lambda. To implement…
Decorator Pattern A decorator pattern allows a user to add new functionality to an existing…
Delegating pattern In software engineering, the delegation pattern is an object-oriented design pattern that allows…
Technology has emerged a lot in the last decade, and now we have artificial intelligence;…
Managing a database is becoming increasingly complex now due to the vast amount of data…
Overview In this article, we will explore Spring Scheduler how we could use it by…