Is it better to use a TreeSet or ArrayList when using a custom comparator

Question

I have implemented a graph. I want to sort a given subset of vertices with respect to their degrees. Therefore, I've written a custom comparator named DegreeComparator.

private class DegreeComparator implements Comparator<Integer>
{
    @Override
    public int compare(Integer arg0, Integer arg1) 
    {
        if(adj[arg1].size() == adj[arg0].size()) return arg1 - arg0;
        else return adj[arg1].size() - adj[arg0].size());
    }

}

So, which one of the below is more efficient?

Using TreeSet

public Collection<Integer> sort(Collection<Integer> unsorted)
{
    Set<Integer> sorted = new TreeSet<Integer>(new DegreeComparator());
    sorted.addAll(unsorted);
    return sorted;
}

Using ArrayList

Collections.sort(unsorted, new DegreeComparator());

Notice that the second approach is not a function, but a one-line code.

Intuitively, I'd rather choose the second one. But I'm not sure if it is more efficient.

Answer 1

Java API contains numerous Collection and Map implementations so it might be confusing to figure out which one to use. Here is a quick flowchart that might help with choosing from the most common implementations

Answer 2

A TreeSet is a Set. It removes duplicates (elements with the same degree). So both aren't equivalent.

Anyway, if what you want naturally is a sorted list, then sort the list. This will work whether the collection has duplicates or not, and even if it has the same complexity (O(n*log(n)) as populating a TreeSet, it is probably faster (because it just has to move elements in an array, instead of having to create lots of tree nodes).