Relative sort - insertBefore() and insertAfter() methods

Question

I need to sort a list who's items are objects that describe how the items should be sorted relative to other items in the same list. The items are loaded dynamically so I have no way of making sure they are ordered to begin with.

What lists should I be looking at? The ArrayList doesn't have methods like insertBefore() or insertAfter(). LinkedLists might but I am not sure if the Java implementation of LinkedLists provide such methods. Any ideas?

Note: I should have clarified that I do not have duplicates in my array...

Answer 1

Instead of writing your own sorting routine, you should use Collections.sort(List,Comparator). This sorts any List using the provided comparator.

You'll need to implement a comparator that will produce the desired ordering.

If this is not applicable to the problem at hand, please clarify your requirements by perhaps providing an example.