Java collection data structure for sorting goods

Question

I have a program that uses ArrayList<T>, and this type of T also implements Comparable<T>. I need to keep this list sorted.

Now, when I insert a new element, I add it to ArrayList, and then call Collections.sort(myArrayList).

Is sorting with Collections.sortevery time I insert a new element seriously hurt the runtime complexity?

Is there a more suitable data structure that I can use to always sort the list? I know the structure called PriorityQueue, but I also need to be able to get list items by index.

EDIT: In my particular case, inserting a new item is much less than getting an existing item, so in the end, good advice could also be left with ArrayList, since it got constant time complexity when getting the item. But if you know anything else ...

Answer 1

It seems that Collection.Sortthis is actually the way to go, because when the collection is almost sorted, sorting will take no more than O (n) in the worst case.

Answer 2

- , , . , , . , . , Sun SortedList TreeList. Collections.sort(..)

Apache TreeList, , . - http://commons.apache.org/proper/commons-collections/javadocs/api-3.2.1/org/apache/commons/collections/list/TreeList.html

Answer 3

Collections.sort(myArrayList) - , , , , .

Collections.sort(myArrayList) 0 (nlogn), O (n), Collections.binarySearch. , Collections.binarySearch , , , (-(insertion point) - 1). Collections.binarySearch ( O (logn)). , , . addAt O (n). addAt, ArrayList O (n) .

Answer 4

A single data structure cannot provide both sorting and index search. If the input data set is limited to a few hundred or thousands, you can store two data structures in parallel.

For example, ArrayList for index search and TreeMap (or priority queue) for sorting.