which container is best for sorting

[H Melua]

hello

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

Hannah

[Paul Sturrock]

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)

[Vijayendra V Rao]

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:

myLinkedList.get(i);

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.

[H Melua]

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 itratr.next() 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:
sortByName()
sortBySurname()
sortByAge()
SortByID()
find(person)
add(person) (<---- makes a call to find!)
remove(person)

so will i be ok with ArrayList?
thanks
hannah
[ January 21, 2005: Message edited by: H Melua ]

[Layne Lund]

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?

Layne