a collection data structure to keep items sorted

Question

I got a program which is using an ArrayList<T> and that type T also implements Comparable<T>. I need to keep that list sorted.

For now, when I insert a new item, I add it to the ArrayList and then invoke Collections.sort(myArrayList).

Is sorting with Collections.sort every time I insert a new item seriously hurt run time complexity?

Is there a better suited data structure I can use to always keep the list sorted? I know of a structure called a PriorityQueue but I also need to be able to get the list's elements by index.

EDIT: In my specific case, inserting a new item happens much less than geting an already existing item, so eventually a good advice could also be to stay with the ArrayList since it got a constant time complexity of getting an item. But if you know of anything else...

Answer 1

It seems like Collection.Sort is actually the way to go here since when the collection is already almost sorted, the sorting will take not longer than O(n) in the worst case.

Answer 2

Instead of using Collections.sort(myArrayList) after every insertion you might want to do something a bit smarter as you know that every time you insert an element your collection is already ordered.

Collections.sort(myArrayList) takes 0(nlogn) time, you could do an ordered insert in an ordered collection in O(n) time using Collections.binarySearch. If the collection is ordered in ascending order Collections.binarySearch returns the index of the element you are looking for if it exists or (-(insertion point) - 1). Before inserting an element you can look for it with Collections.binarySearch (O(logn) time). Done that you can derive the index at which inserting the new element. You can then add the element with addAt in O(n) time. The whole insertion complexity is bounded by the addAt so you can do an ordered insert in an ArrayList in O(n) time.

Answer 3

List is an ordered collection, which means you need to have the ability to access with index. If a collection internally shuffles or sorts the elements, the insertion order wont be same as the order of the elements in the internal data structure. So you cannot depend on index based access anymore. Hence Sun didn't provide a SortedList or a TreeList class. That is why you use Collections.sort(..)

Apache commons-collections does provide a TreeList class but it is not a sorted List and is called so because it uses a tree data structure to store the elements internally. Check its documentation here - http://commons.apache.org/proper/commons-collections/javadocs/api-3.2.1/org/apache/commons/collections/list/TreeList.html