Remove duplicates from unsorted linked list java
Type your search query and hit enter: All Rights ReservedView Non-AMP Version Dinesh on JavaType your search query and hit enter:
Remove Duplicates from the Unsorted Singly Linked listIn 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. Show
Lets discuss how to Remove Duplicates from the Unsorted Singly Linked list. Remove Duplicates from the Unsorted Singly Linked listIn the following diagram, you can see the approach: Here, we have an unsorted singly linked list, we have to write a program to remove the duplicates from an unsorted linked list. Approach 1: We can use two loopsStep 1: In the first loop, hold each node data. Step 2: In the second inner loop, we can match each node withhold data from the first loop. Step 3: If node data is repeated, then delete that data. This approach has O(n^2) time complexity. Lets see the second approach with the O(n) time complexity as the following: Approach 2: Using HashmapIn this approach, we create a hashmap and using this hashmap we can remove duplicates from the unsorted singly Linked list. Step 1: Create a HashMap As we can see this approach reduces the time complexity to O(n) but increases the space complexity by O(n). In my point of view, this approach much better than approach 1. Lets see the complete code: The algorithm in java code as the below: /** * */ 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; MapRun above program, you will get the following output: Original List : ->1->2->2->4->5->4->3 Updated List: ->1->2->4->5->3In this example, we have written a program to remove duplicates from the unsorted singly linked list Hope, you have understood this solution. Please share other solutions if you have. :). Happy learning with us!!!. Previous Next Share this:Dinesh Rajput Dinesh Rajput is the chief editor of a website Dineshonjava, a technical blog dedicated to the Spring and Java technologies. It has a series of articles related to Java technologies. Dinesh has been a Spring enthusiast since 2008 and is a Pivotal Certified Spring Professional, an author of a book Spring 5 Design Pattern, and a blogger. He has more than 10 years of experience with different aspects of Spring and Java design and development. His core expertise lies in the latest version of Spring Framework, Spring Boot, Spring Security, creating REST APIs, Microservice Architecture, Reactive Pattern, Spring AOP, Design Patterns, Struts, Hibernate, Web Services, Spring Batch, Cassandra, MongoDB, and Web Application Design and Architecture. He is currently working as a technology manager at a leading product and web development company. He worked as a developer and tech lead at the Bennett, Coleman & Co. Ltd and was the first developer in his previous company, Paytm. Dinesh is passionate about the latest Java technologies and loves to write technical blogs related to it. He is a very active member of the Java and Spring community on different forums. When it comes to the Spring Framework and Java, Dinesh tops the list! Next How to Detect loop in a linked list » Previous « Singly linked list is palindrome without extra space Leave a Comment Share Published by Dinesh Rajput
Related PostRecent Posts
Spring Batch Read from CSV and write to relational DBIn Spring Batch, we often need read data from CSV file and write it into 11 months ago
A Practical Example of Hexagonal Architecture in JavaHexagonal architecture is an application design pattern. It solves some problems of the layered architecture 2 years ago
Send emails in JavaToday we will discuss how to send emails from your Java app. In general, you 2 years ago
Create a Data Structure GetMostFrequent of O(1)In this article, we will discuss how to create a Data Structure with Insert, Delete 2 years ago
Least Frequently Used (LFU) Cache ImplementationIn this article, we will discuss how to design and implement a Least Frequently Used 2 years ago
Implement LRU cache algorithm in JavaIn this article, we will discuss how to design and implement an LRU cache algorithm 2 years ago All Rights ReservedView Non-AMP Version
|