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.

Study note: how the limitless nonvolatile memory will affect the future of world

I am studying the MSc of IT programme in Liverpool University. This week we discussed how the limitless nonvolatile memory will affect the future of world.


Below is the discussion summary of what I wrote to forum wtoday:


Hi All,

Super large but cheap storage device is not a dream in the coming future, but to keep the stored data organized is also the necessary thing we have to bear in mind. I think the problem is not how large of the storage capacity, it is because we misuse the large storage device, and the lack of softwares to help organize the large amount of documents, photos or binary files.

Vee mentioned a key point of these large amount of documents or images - metadata. Everyone knows the concept of web 2.0. It is a popular marketing phrase we can see in the Internet. If we can't organize data well, even 10MB data we could mess it up. Web 2.0 emphasize the interaction among Internet users, people contribute everything into many kinds of web 2.0 model web site, e.g. Del.icio.us, Flicker. Everytime you bookmark or upload something, you have to give metadata to your documents or photos, thus the sofrware, might be a search engine or something like that, behind the user interface can start to analyze the new uploaded document, and associate these data by many kinds of algorism. I would say that the 20th century is the era of data collecting century; and the 21th century is the era of data manipulating. So many ERP systems were built in the last century, these data are collected large enough to start predicting trends, analyzing behavior or something else. Thus who owns the most powerful search engine or analyzing algorism, who will lead the business of 21th century. So a stong back bone hardware to support these large raw data or results is the same important.

A reliable, fast, large, and reasonable price sotrage device is the foundation to support the everything above make make true in the future.