Remove duplicates from an unsorted linked list in Java.

Remove duplicates from an unsorted linked list in Java..

---

Given an unsorted linked list, Remove duplicates from it.

Lets see sample input and output for better understanding:

Algorithm 

---

We will see two approaches to remove duplicates from the unsorted linked list.

Approach 1: Using Set:
Iterate the linked list and compare it with data present on the Set, if the data is present on the Set then that node is the duplicate node and skip it in the list.
If it its not present on the Set, then it is unique, so put it on Set as indication that is visited once.

Approach 2: O(N^2):

Iterate the list, pick the first node and compare it with all the node of the list, if the node is matched then skip it from the list else not.
Repeat the check for all the nodes of the linked list.

Java Program to Remove duplicates from an unsorted linked list.

---

package com.javabypatel.linkedlist;

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

public class RemoveDuplicatesFromUnsortedList {
    LinkedListNode startNode;

    public static void main(String[] args) {
        RemoveDuplicatesFromUnsortedList obj = new RemoveDuplicatesFromUnsortedList();
        obj.addNode(new LinkedListNode(10));
        obj.addNode(new LinkedListNode(20));
        obj.addNode(new LinkedListNode(10));
        obj.addNode(new LinkedListNode(20));
        obj.addNode(new LinkedListNode(10));

        //Print List
        System.out.println("Original List is: ");
        obj.printLinkList(obj.startNode);
        System.out.println();

        obj.removeDuplicates(obj.startNode);
        System.out.println("List after removing duplicates:");
        obj.printLinkList(obj.startNode);
        System.out.println();

        //        obj.removeDuplicatesUsingHashMapApproach1(obj.startNode);
        //        System.out.println("List after removing duplicates using Set Approach1:");
        //        obj.printLinkList(obj.startNode);
        //        System.out.println();

        //        obj.removeDuplicatesUsingHashMapApproach2(obj.startNode);
        //        System.out.println("List after removing duplicates using Set Approach2:");
        //        obj.printLinkList(obj.startNode);
        //        System.out.println();
    }


    //time complexity: O(n^2)
    //Remove the duplicates in a way we do selection sort,
    //pick one node and remove all the duplicates matching that node data in the list
    //pick next node and remove all the duplicates matching that node data in the list and so on.
    private void removeDuplicates(LinkedListNode startNode) {
        LinkedListNode temp = startNode;
        while (temp != null) {

            LinkedListNode currNode = temp;
            while (currNode.getNext() != null) {
                if (currNode.getNext().getData() == temp.getData()) {
                    currNode.setNext(currNode.getNext().getNext());
                    //Do not go to next node, so that next node which we just changed is yet to examine for duplication.
                } else {
                    //go to next node
                    currNode = currNode.getNext();
                }
            }
            temp = temp.getNext();
        }
    }

    //time complexity: O(n)
    private void removeDuplicatesUsingHashMapApproach1(LinkedListNode startNode) {
        if (startNode == null || startNode.getNext() == null) {
            return;
        }

        Set set = new HashSet<>();
        set.add(startNode.getData());

        //First node is always unique, start comparing from second node before that put
        //first node data in set marking as already read.
        while (startNode.getNext() != null) {
            if (set.contains(startNode.getNext().getData())) {
                startNode.setNext(startNode.getNext().getNext());
            } else {
                set.add(startNode.getNext().getData());
                startNode = startNode.getNext();
            }

        }
    }

    //time complexity: O(n)
    private void removeDuplicatesUsingHashMapApproach2(LinkedListNode startNode) {
        if (startNode == null || startNode.getNext() == null) {
            return;
        }

        Set set = new HashSet<>();

        LinkedListNode previousNode = null;
        while (startNode != null) {
            if (set.contains(startNode.getData())) {
                startNode = startNode.getNext();
                previousNode.setNext(startNode);
            } else {
                set.add(startNode.getData());
                previousNode = startNode;
                startNode = startNode.getNext();
            }
        }
    }

    private void printLinkList(LinkedListNode startNode) {
        LinkedListNode tempNode = startNode;
        while (tempNode != null) {
            System.out.print(tempNode.getData() + " ");
            tempNode = tempNode.getNext();
        }
    }

    private void addNode(LinkedListNode node) {
        if (startNode != null) {
            LinkedListNode tempNode = startNode;
            while (tempNode.getNext() != null) {
                tempNode = tempNode.getNext();
            }
            tempNode.setNext(node);
        } else {
            this.startNode = node;
        }
    }
}

You may also like to see

---

Sort Linked list using Merge sort

Bubble Sort

Heap Sort

Selection Sort

Insertion Sort

---

How ConcurrentHashMap works and ConcurrentHashMap interview questions

How Much Water Can A Bar Graph with different heights can Hold

Interview Questions-Answer Bank

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.