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...

Could you provide a more concrete example of what you're trying to accomplish? — aioobe, Oct 05 '11 at 14:36

NPE · Accepted Answer · 2011-10-05T14:42:18.617

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.

edited Oct 05 '11 at 14:42

answered Oct 05 '11 at 14:36

NPE

486,780
108
951
1,012

1

Reading the OP's question, I get the feeling he's dealing with strings such as `"I should come before X"`, "`I should come after Y`", `"X"`, `"Y"`. If this is the case, a comparator won't do. – aioobe Oct 05 '11 at 14:40
No, that's not the case actually. I don't have to parse any strings. – Ayyoudy Oct 05 '11 at 17:50

score 1 · Answer 2 · answered Oct 05 '11 at 14:38

1

The ArrayList doesn't have methods like insertBefore() or insertAfter().

No, but it does have indexOf(o) and add(o, index) which should be sufficient for easily implementing insertBefore and insertAfter.

answered Oct 05 '11 at 14:38

aioobe

413,195
112
811
826

score 1 · Answer 3 · edited May 23 '17 at 09:59

1

If you want to insert new items, and keep the collection sorted, you can use priorty queue class in Java. Sets will not allow you to store duplicates. For more information about priority queue, you can look at this answer

Sorted collection in Java

edited May 23 '17 at 09:59

Community

1
1

answered Oct 05 '11 at 14:41

reader_1000

2,473
17
15

vote up! It's the easiest - just use *PriorityQueue*, fastest - O(logN) and duplicate allow. – 卢声远 Shengyuan Lu Oct 05 '11 at 14:53

score 0 · Answer 4 · answered Oct 05 '11 at 14:37

0

Try the SortedSet class.

If you implement the Comparable interface correctly it will automatically sort it for you.

answered Oct 05 '11 at 14:37

Sarel Botha

12,419
7
54
59

1

Doesn't allow duplicates though. – aioobe Oct 05 '11 at 14:39

score 0 · Answer 5 · answered Oct 05 '11 at 14:39

0

If you can make the obejcts implement Comparable, then calling Collections.sort(myArrayList) will sort out any List object including ArrayList.

Alternatively use Collections.sort(myArrayList, myComparator) with an approipriate Comparator

answered Oct 05 '11 at 14:39

Matt Fellows

6,512
4
35
57

Relative sort - insertBefore() and insertAfter() methods

5 Answers5