Question

Q2 [15 pts] Linked list: For this question use class Node.java

Assume this file implements a node in a linked list. It has the following public data members:

➢ int data

➢ Node next

Write class Node and Class single linked list then write the following functions:

2.2 Remove duplicates from an unsorted linked list Write a Java method removeDuplicates()

which takes a list and deletes any duplicate nodes from the list. The list is not sorted.

Example:

if the linked list is 12->11->12->21->41->43->21 then removeDuplicates() should convert the list to 12->11->21->41->43.

Answer 1

Here is your code. I created some extra method for checking list easily. You can remove it, if you don't need it really.

Node.java

//Created node class with two data member.
public class Node {
    int data;
    Node next;
}

SingleLinkedList.java

import java.util.HashSet;

//Created SingleLinkedList with a constructor and
//and one few method extra for adding and printing list.
public class SingleLinkedList {
    //Start node, where list get started.
    private Node head;
    //The current node, which hold the current reference.
    private Node currenNode;

    //One initialize it takes data and put in head node.
    //and this head node is our current node too.
    public SingleLinkedList(int data){
        head = new Node();
        head.data = data;
        head.next = null;
        currenNode = head;
    }

    //This is optional method, not asked in question.
    //It is for adding new item to list.
    public void addItem(int data){
        //Create a node for this item.
        Node newNode = new Node();
        //put the data.
        newNode.data = data;
        //now point our current's next node to this node.
        currenNode.next = newNode;
        //and finally make this node as a current node.
        currenNode = newNode;
    }

    //Optional method that will return the reference for this
    //single linked list. Remember, only head node stores
    //start reference of our list.
    public Node getSingleLinkedList(){
        return head;
    }

    //This method remove the duplicated.
    public void removeDuplicates(Node node){
        //First create a temp node i.e. current
        Node current = node;
        //Create hashSet of integer to store the node's data.
        //In which we will look every time for duplicate data.
        HashSet<Integer> integers = new HashSet<>();

        //Now put the current node data to hashSet.
        integers.add(current.data);

        //Iterate through every node. until current.next not equals
        //to null.
        while (current.next != null){
            //check if next node's data is in hashSet or not.
            //If yes, it means this data already comes before this node.
            if(integers.contains(current.next.data)){
                //skip next node of current node.
                //by making current next node equals to
                // current.nextNode.nextNode.
                current.next = current.next.next;
            }else{
                //If data is unique, add to hash set,
                //and point current node to current.next node.
                integers.add(current.next.data);
                current = current.next;
            }
        }
    }

    //Simple method to print every node from the list.
    public void printList(){
        Node current = head;
        while (current.next != null){
            System.out.print(current.data + "->");
            current = current.next;
        }
        System.out.println(current.data);

    }
}

Main.java(Driver Class)

public class Main {

    public static void main(String[] args) {
       SingleLinkedList linkedList = new SingleLinkedList(12);
       linkedList.addItem(11);
       linkedList.addItem(12);
       linkedList.addItem(21);
       linkedList.addItem(41);
       linkedList.addItem(43);
       linkedList.addItem(21);
       linkedList.printList();

       linkedList.removeDuplicates(linkedList.getSingleLinkedList());

       linkedList.printList();
    }
}

Output