Code review for style, clarity and efficiency. Removing duplicates from linkedlist

Question

import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

class RemoveDuplicates {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<Integer>();
        list.add(1);
        list.add(1);
        list.add(1);
        list.add(4);
        System.out.println(RemoveDuplicates.rmDuplicates(list));
    }

    public static List<Integer> rmDuplicates(List<Integer> list) {
        Collections.sort(list);
        Iterator<Integer> it = list.iterator();
        int index = 0;
        while (it.hasNext() && index < list.size() - 1) {
            int current = it.next();
            index++;
            if (current == list.get(index)) {
                it.remove();
                index--;
            }
        }
        return list;
    }
}

Update: I did not want a sorted list. Just removing duplicates is enough and I wanted it in place. I thought without sorting it would be tricky to remove duplicates.

Answer 1

LinkedList is designed to preserve the order in which elements were inserted into it above all other considerations. It should only be used when you need to retrieve the items in the list in order, because there is a faster collection available for any other type of access.

It looks from your code like you want a sorted list of elements, in addition to duplicates removed as stated in your question. Sets are designed to have no duplicates and TreeSet is designed to sort your items as they are inserted. If you use a TreeSet instead of a LinkedList you don't need a rmDuplicates method at all! If you are concerned about returning a Set instead of a List, you can always return a Collection because it has about the same signature. Time the difference between your method and using a TreeSet with a hundred thousand elements. I think you will be surprised how fast TreeSet is!

public static void main(String[] args) {
    TreeSet<Integer> list = new TreeSet<Integer>();
    list.add(1);
    list.add(1);
    list.add(1);
    list.add(4);
    System.out.println(list);
}

If you needed to preserve the insertion order, I'd use a LinkedHashSet:

public static Collection<Integer> rmDuplicates(Collection<Integer> list) {
    return new LinkedHashSet(list);
}

If you have tried this with a custom type of Object instead of an integer and it didn't work, then you need to implement equals(), hashcode(), and maybe compareTo() properly.

Answer 2

I would not save keystrokes by calling your method rmDuplicates, I would simply call it removeDuplicates.

Using both an Iterator and an index means you're probably doing it wrong.

If you did not have to modify the provided list, I would do the following:

LinkedList<Integer> helperList = new LinkedList<Integer>();
Iterator<Integer> it = list.iterator();
while (it.hasNext()) {
  Integer current = it.next();
  if( !helperList.contains( current ) ){
    helperList.add( current )
  }
}
return helperList;

As the other reviewer pointed out, your method also sorts the list, do not assume that sorting a provided list is harmless.