Sort a list of objects to put parents first I have a class which contains a reference to a parent of the same type( or null if it has no parent).


class MyObject{
    private MyObject parent;
    public MyObject getParent(){ return parent};
    …
}



I have a list of MyObject, and need to order it so that every object comes after its parent in the list (the parent will always be in the list). 

void orderList(List&lt;MyObject&gt; toSort){
    List&lt;MyObject&gt; tmp = new ArrayList&lt;&gt;();
    while(!toSort.isEmpty()) {
        for(MyObject obj: toSort){
            if(obj.getParent() == null) {
                tmp.add(obj);
            }else {
                if(tmp.contains(obj.getParent())) {
                    tmp.add(obj);
                }
            }
        }
        toSort.removeAll(tmp);
    }
    toSort.addAll(tmp);
}


Is there a way to make this function more efficient and readable ?
You can make this faster quite a bit (in complexity terms) by precomputing which objects have which parent and then successively building your list instead of iterating all objects with pure chance. Your complexity in the worst case right now is \$O(n^3)\$. (n^2 for the nested loops, another n for the contains)

Consider the following:

void orderList(List&lt;MyObject&gt; toSort) {
    final MyObject nullPlaceholder = new MyObject();
    Map&lt;MyObject, List&lt;MyObject&gt;&gt; byParent = toSort.stream()
         .collect(Collectors.groupingBy(obj -&gt; 
           (obj.getParent() == null ? nullPlaceholder : obj.getParent())
           , Collectors.toList()));

    List&lt;MyObject&gt; ordered = new ArrayList&lt;&gt;();
    Queue&lt;MyObject&gt; processor = new LinkedList&lt;&gt;();
    byParent.get(nullPlaceholder).forEach(processor::add);
    while (!processor.isEmpty()) {
        MyObject tmp = processor.poll();
        byParent.getOrDefault(tmp, Collections.emptyList())
          .forEach(processor::add);
        ordered.add(tmp);
    }
    toSort.clear();
    toSort.addAll(ordered);
}


Notes:


You menitioned in comments, that null-keys are not supported in the groupingBy collector. This code works around by creating a "null object". more info at wikipedia
getOrDefault works around the fact that the last MyObjects won't have "children", meaning that they don't have elements in the map. With standard get that would return null. You could manually check, but that breaks the flow IMO, and I prefer it like this :)


This should boil down to a runtime complexity of \$O(n)\$, which should give you significant performance boosts for larger lists.

In addition to that I dislike reusing references you receive as input. I personally prefer to use value-returning methods instead of modifying references. As such I'd adjust your method to return a List&lt;MyObject&gt; and return ordered; at the end.