1

I'm looking for a collection that maintains sorted order as well as index access. My program will have hundreds of thousands of iterations, so I don't want to keep calling Collections.sort, as that would be too costly.

questioner and answerer
  • 680
  • 3
  • 15
  • 1
    for a good discussion why there exists no standard JDK sorted list see http://stackoverflow.com/questions/8725387/why-is-there-no-sortedlist-in-java – wero Sep 06 '15 at 18:37
  • 1
    See this q/a: http://stackoverflow.com/questions/4031572/sorted-array-list-in-java – aioobe Sep 06 '15 at 18:38
  • You can use binary search to insert in an ArrayList while maintaining order e.g. [here](http://stackoverflow.com/a/3602046/1413133) – Manos Nikolaidis Sep 06 '15 at 18:39

1 Answers1

2

None of the standard collections that come with Java supports this, but you can implement your own.

One way to implement such a collection would be to use a sorted array. Index lookups are easy. Value lookups could use Arrays.binarySearch(). Inserting a new value would also use binarySearch() to find the insertion point, then shift the remainder of the values to make room for the new value, auto-extending the array as needed.

Andreas
  • 154,647
  • 11
  • 152
  • 247