Removing duplicate elements from a LinkedList in Java

Question

I've been working on an assignment that allows a user to enter Objects into a LinkedList, as well as remove them. I have all areas of my program figured out except this pesky part here... removing duplicates. I've been at this for some time now, and was hoping somebody could point me in the right direction.

The code I have below almost works... as in it does delete the duplicates... but only of the first element it encounters. So, how do I allow the program to look at the first item, delete its duplicates, and then go back and do the same for all the other elements in the list? Should I be using Nodes like "previous" and "current" rather than what I'm getting at here, and attempt to traverse the LinkedList that way? I was hinted by my professor that two while loops are needed, but all the ways I've tried it have not worked properly. What am I supposed to put as the parameter for the second, and I'm assuming, outer while loop?

Any help is greatly appreciated, thanks!

public void removeDuplicate() //searches the LinkedList for duplicate elements, and removes them
   {
   ListIterator iter = listIterator();

   Object uniqueO = iter.next();

        while (iter.hasNext())
        {
           String uniqueS = (String) uniqueO;
           Object compareO = iter.next();
           String compareS = (String) compareO;
           int x = uniqueS.compareTo(compareS);
           if (x == 0)
           {
               iter.remove();
           }
        }

} //end removeDuplicate

Answer 1

it should be a set way . But if you don't want to change the original order , this can help:

//here, you can consider set as just a data structure which never tolerate duplicates :)

     public void removeDuplicate() //searches the LinkedList for duplicate elements, and removes them
   {
   ListIterator iter = listIterator();

    HashSet tempSet = new HashSet();


        while (iter.hasNext())
        {

        Object obj = iter.next();
                      if(tempSet.contains(obj))){
                          iter.remove();
                      }else{
                            tempSet.add(obj);
                      }
        }

} //end removeDuplicate

Answer 2

If space is not a concern, you can always copy it to a new list, verifying before insertion that it is not yet in the new list:

public static LinkedList<Object> dedup(LinkedList<Object> original) {
    LinkedList<Object> copy = new LinkedList<Object>();

    for (Object o : original) {
        if (!copy.contains(o)) {
            copy.add(o);
        }
    }

    return copy;
}

You have stated that you already have an add function working, and you can implement a simple contains function fairly easily, for your LinkedList class:

public boolean contains(Object o) {
    ListIterator iter = listIterator();

    while (iter.hasNext()) {
        if (iter.next().equals(o)) {
            return true;
        }
    }

    return false;
}