Dinesh on Java
- Homepage
- interview questions
- Algorithms
Remove Duplicates from the Unsorted Singly Linked list
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.
Lets have a look at the following more algorithms related the linked list:
- Find the nth node from the end of a singly linked list
- Find the middle element in a linked list
- How to Reverse linked list in Java
- Delete given node from a singly linked list
- A singly linked list is palindrome without extra space
Lets discuss how to Remove Duplicates from the Unsorted Singly Linked list.
Remove Duplicates from the Unsorted Singly Linked list
In 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 loops
Step 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 Hashmap
In 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
Step 2: Lets consider two pointers such as prevNode and currNode.
Step 3: Lets initialize these pointers as prevNode = head and currNode = head.next.
Step 4: Iterate this linked list and check every node data is present in the HashMap.
Step 5: If No, then insert that node data into the HashMap as the key.
Step 6: If Yes, then delete that node using prevNode and currNode.
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; Map 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; } } }Run 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!!!.
Share this:
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!
- Create a Data Structure GetMostFrequent of O[1]
In this article, we will discuss how to create a Data Structure with Insert, Delete
- Least Frequently Used [LFU] Cache Implementation
In this article, we will discuss how to design and implement a Least Frequently Used
- Implement LRU cache algorithm in Java
In this article, we will discuss how to design and implement an LRU cache algorithm
Related Post
Recent Posts
- Spring Batch
- Tutorial
Spring Batch Read from CSV and write to relational DB
In Spring Batch, we often need read data from CSV file and write it into
- Design Pattern
A Practical Example of Hexagonal Architecture in Java
Hexagonal architecture is an application design pattern. It solves some problems of the layered architecture
- JavaMail
Send emails in Java
Today we will discuss how to send emails from your Java app. In general, you
- Algorithms
Create a Data Structure GetMostFrequent of O[1]
In this article, we will discuss how to create a Data Structure with Insert, Delete
- Algorithms
Least Frequently Used [LFU] Cache Implementation
In this article, we will discuss how to design and implement a Least Frequently Used
- Algorithms
Implement LRU cache algorithm in Java
In this article, we will discuss how to design and implement an LRU cache algorithm
- t
- L