<p>In this article, we will discuss another algorithm related to the singly linked list, how to remove duplicates from the unsorted singly linked list. A singly linked list has several nodes, and each node in the list has the content and a pointer to the next node in the list. It does not store any pointer to the previous node.</p>
<blockquote><p>Let&#8217;s have a look at the following more algorithms related the linked list:</p>
<ul>
<li><strong><a href="https://dineshonjava.com/nth-node-from-the-end-of-a-singly-linked-list/">Find the nth node from the end of a singly linked list</a></strong></li>
<li><strong><a href="https://dineshonjava.com/find-the-middle-element-in-a-linked-list/">Find the middle element in a linked list</a></strong></li>
<li><strong><a href="https://dineshonjava.com/reverse-linked-list/">How to Reverse linked list in Java</a></strong></li>
<li><strong><a href="https://dineshonjava.com/delete-given-node-from-singly-linked-list/">Delete given node from a singly linked list</a></strong></li>
<li><strong><a href="https://dineshonjava.com/singly-linked-list-is-palindrome/">A singly linked list is palindrome without extra space</a></strong></li>
</ul>
</blockquote>
<p>Let&#8217;s discuss how to Remove Duplicates from the Unsorted Singly Linked list.</p>
<h2>Remove Duplicates from the Unsorted Singly Linked list</h2>
<p>In the following diagram, you can see the approach:</p>
<p><img class="aligncenter size-full wp-image-4275" src="https://dineshonjava.com/wp-content/uploads/2018/09/delete-duplicates-from-single-linked-list-java-1.jpg" alt="Remove Duplicates from the Unsorted Singly Linked list" width="522" height="115" /></p>
<p>Here, we have an unsorted singly linked list, we have to write a program to remove the duplicates from an unsorted linked list.</p>
<h3>Approach 1: We can use two loops</h3>
<p><strong>Step 1:</strong> In the first loop, hold each node data.</p>
<p><strong>Step 2:</strong> In the second inner loop, we can match each node withhold data from the first loop.</p>
<p><strong>Step 3:</strong> If node data is repeated, then delete that data.</p>
<p>This approach has <strong>O(n^2) time complexity</strong>. Let&#8217;s see the second approach with the O(n) time complexity as the following:</p>
<h3>Approach 2: Using Hashmap</h3>
<p>In this approach, we create a hashmap and using this hashmap we can remove duplicates from the unsorted singly Linked list.</p>
<p><strong>Step 1:</strong> Create a HashMap<br />
<strong>Step 2:</strong> Let&#8217;s consider two pointers such as prevNode and currNode.<br />
<strong>Step 3:</strong> Let&#8217;s initialize these pointers as prevNode = head and currNode = head.next.<br />
<strong>Step 4:</strong> Iterate this linked list and check every node data is present in the HashMap.<br />
<strong>Step 5:</strong> If No, then insert that node data into the HashMap as the key.<br />
<strong>Step 6:</strong> If Yes, then delete that node using prevNode and currNode.</p>
<p>As we can see this approach reduces the <strong>time complexity to O(n)</strong> but increases the <strong>space complexity by O(n)</strong>. In my point of view, this approach much better than approach 1.</p>
<p>Let&#8217;s see the complete code:</p>
<pre>package com.dineshonjava.algo; 
 
/** 
 * @author Dinesh.Rajput 
 * 
 */ 
public class Node { 
	 
 Node next; 
 String data; 
 
 public Node(String data) { 
	super(); 
	this.data = data; 
 } 
} 
 
</pre>
<p><strong>The algorithm in java code as the below:</strong></p>
<pre>/** 
 * 
 */ 
package com.dineshonjava.algo; 
 
import java.util.HashMap; 
import java.util.Map; 
 
/** 
 * @author Dinesh.Rajput 
 * 
 */ 
public class RemoveDuplicateLinkedList { 
 
	/** 
	 * @param args 
	 */ 
	public static void main(String[] args) { 
		 
		Node head = new Node("1"); 
		head.next = new Node("2"); 
		head.next.next = new Node("2"); 
		head.next.next.next = new Node("4"); 
		head.next.next.next.next = new Node("5"); 
		head.next.next.next.next.next = new Node("4"); 
		head.next.next.next.next.next.next = new Node("3"); 
 
		System.out.println("Original List : "); 
 display(head); 
 
 System.out.println("\nUpdated List: "); 
 Node update = deDup(head); 
 display(update); 
	} 
	 
	private static Node deDup(Node head) { 
		 
		if(head == null || head.next == null) { 
			return head; 
		} 
		 
		Node prevNode = head; 
		Node currNode = head.next; 
		Node temp = null; 
		 
		Map<;String, Integer>; map = new HashMap<;>;(); 
		 
		map.put(prevNode.data, 1); 
		 
		while(currNode != null) { 
		 
			if(map.containsKey(currNode.data)) { 
				temp = currNode; 
				prevNode.next = currNode.next; 
				currNode = currNode.next; 
				temp = null; 
			}else { 
				map.put(currNode.data, 1); 
				prevNode = currNode; 
				currNode = currNode.next; 
			} 
			 
		} 
		return head; 
	} 
 
	private static void display(Node head){ 
 Node n=head; 
 while(n!=null){ 
 System.out.print("->;" + n.data); 
 n=n.next; 
 } 
	} 
 
} 
 
 
</pre>
<p>Run above program, you will get the following output:</p>
<pre>Original List : 
->;1->;2->;2->;4->;5->;4->;3 
Updated List: 
->;1->;2->;4->;5->;3 
</pre>
<p>In this example, we have written a program to remove duplicates from the unsorted singly linked list</p>
<p>Hope, you have understood this solution. Please share other solutions if you have. :).</p>
<p>Happy learning with us!!!.</p>
<div align="center"><iframe style="width: 120px; height: 240px;" src="//ws-in.amazon-adsystem.com/widgets/q?ServiceVersion=20070822&;OneJS=1&;Operation=GetAdHtml&;MarketPlace=IN&;source=ac&;ref=qf_sp_asin_til&;ad_type=product_link&;tracking_id=dineshonjav06-21&;marketplace=amazon&;region=IN&;placement=1788299450&;asins=1788299450&;linkId=05b0146b0a85f4472697901e353dc276&;show_border=true&;link_opens_in_new_window=true&;price_color=333333&;title_color=0066c0&;bg_color=ffffff" frameborder="0" marginwidth="0" marginheight="0" scrolling="no"><br />
</iframe></div>
<div class="wp-post-navigation"> 
									 <div class="wp-post-navigation-pre"> 
									 <a href="https://dineshonjava.com/singly-linked-list-is-palindrome/">Previous</a> 
									 </div> 
									 <div class="wp-post-navigation-next"> 
									 <a href="https://dineshonjava.com/how-to-detect-loop-in-a-linked-list/">Next</a> 
									 </div> 
									</div>
<script type="text/javascript">
jQuery(document).ready(function($) {
 $.post('https://dineshonjava.com/wp-admin/admin-ajax.php', {action: 'mts_view_count', id: '4272'});
});
</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…