File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
The moose likes Beginning Java and the fly likes which container is best for sorting Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "which container is best for sorting" Watch "which container is best for sorting" New topic

which container is best for sorting

H Melua
Ranch Hand

Joined: Jan 04, 2005
Posts: 172

when working with collections (ArrayList, LinkedList, Vector) which of these is the most suitable to use if u need to iterate through the array to sort it?? and please indicate why ..

Paul Sturrock

Joined: Apr 14, 2004
Posts: 10336

Well lets dismiss Vector straight away, since you shouldn't be using it.

LinkedLists offer best sequential access. A bigger hit on the performance of a sort though will be the sort algorithm you use, not what you are sorting. (Disclaimer: these are just general comments - if you want to know for sure, write a test app and profile performance yourself)

JavaRanch FAQ HowToAskQuestionsOnJavaRanch
Vijayendra V Rao
Ranch Hand

Joined: Jul 04, 2004
Posts: 195
If you are looking for a good container for sorting purposes, I suggest you go with ArrayList. Most of the sorting algorithms access elements on the container that they act on in a non-linear manner. So if the sorting code makes a call to something like:


then this will always start the iteration from the beginning of the LinkedList (unless i > myLinkedList.size()/2) unlike the ArrayList. If your container is large with many Objects in it, then this will turn out to be a performance killer! So, if you are looking for a sorting container, then go with ArrayList.

This is one of the reasons, if you see, ArrayList implements the RandomAccess interface and LinkedList does not.

Vijayendra <br /> <br />"The harder you train in peace, the lesser you bleed in war"
H Melua
Ranch Hand

Joined: Jan 04, 2005
Posts: 172
thanks to u all

im using at the moment ArrayList and sorting it using collections.sort(), but i just want to make sure that i chose the right one.
other than the 4 sorting orders that i have, ive got find(person) method, and there, i used to go through the list and find the element.. but doesnt that mean it will start from the beginning anyway like it is with LinkedList?

im actually confused between them 2!!! these are the methods i have:
add(person) (<---- makes a call to find!)

so will i be ok with ArrayList?
[ January 21, 2005: Message edited by: H Melua ]
Layne Lund
Ranch Hand

Joined: Dec 06, 2001
Posts: 3061
Collections.sort() takes a List as an argument, so you can easily use either ArrayList or LinkedList. This brings me to wonder if there are any behind-the-scenes optimizations for each type of list. Or at the very least, does the algorithm avoid the pitfalls associated with trying to randomly access elements in a LinkedList?


Java API Documentation
The Java Tutorial
I agree. Here's the link:
subject: which container is best for sorting
It's not a secret anymore!