Home » Algorithm » Datastructure » Interviews » Linked List » Remove duplicates from an unsorted linked list in Java.

Remove duplicates from an unsorted linked list in Java.

in , , , - on 02:02:00 - No comments

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;
        }
    }
}
Categories: , , ,

Post a Comment