SortedList lets you get(i) to get the ith item in sorted order, and that's as fast as a TreeSet contains. It also splays so near each other faster the second+ time called. I use this for UIs that do scrolling/paging, and for models/view s that need to query ordered data. For example I have messages coming in real time, put them in a sorted list by importance, and display with a simple list view. Each time a new message comes in, it's lg time to update the view regardless of how long it is.