A Linked List Sorter

About sorting LinkedList, I just implemented a sotrer class two weeks ago because I was asked how to sort a linked list. I tried to write a Java class to sort LinkedList.
Here is my implementation, just for everyone reference, and please advise if any mistake.

Suppose we have a data structure just as below, upper part display origional position, we have to sort out a sequence as lower part.
(Element has null parent ID means it is the first/top one)


First of all, I define an Interface as below:

public interface SortingElement {

Long getId();
Long getParentId();
void setParentId(Long parentId);

}

A sorting element is composed of two value, one is my id, the other is the id which I am linking to (that means parentId). So we have getId() and a pair of setter and getter for parentId.

Following is the LinkedListSorter class:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public final class Sorter {

public static List sort(List elements) {

List rs = new ArrayList();
Map temp = new HashMap();
SortingElement currentElement = null;
for (SortingElement element : elements) {
Long parentId = element.getParentId();
if (parentId != null)
temp.put(element.getParentId(), element);
else
currentElement = element;
}

for (int i=0; i<elements.size(); i++) {
Long childParentId = currentElement.getId();
SortingElement child = temp.get(childParentId);
rs.add(currentElement);
currentElement = child;
}
return rs;
}
}


Before passing List of SortingElement into sorter, we have a pre-condition has to be satisfied, that is only one element can return a null parent id, it means it sits at the top of these elements, others elements must contain its parent id.

Gets into the method, first of all these parent Id value of each elements are extracted out, they are put into a Map which using parent Id as key and element itsself as value.

Then a List is used to sequentially retrieve element from Map according each elements parent Id.

I didn't test its efficiency, but at least it seems works up to now by my test case. Attached is the test Java class, just for you are interested in it.