A good Sorted List for Java

Question

I'm looking for a good sorted list for java. Googling around give me some hints about using TreeSet/TreeMap. But these components is lack of one thing: random access to an element in the set. For example, I want to access nth element in the sorted set, but with TreeSet, I must iterate over other n-1 elements before I can get there. It would be a waste since I would have upto several thousands elements in my Set.

Basically, I'm looking for some thing similar to a sorted list in .NET, with ability to add element fast, remove element fast, and have random access to any element in the list.

Has this kind of sorted list implemented somewhere? Thanks.

Edited

My interest in SortedList grows out of this problems: I need to maintains a list of many thousands object (and can grow up to many hundred of thousands). These objects will be persisted to database. I want to randomly select few dozens of element from the whole list. So, I tried to maintain a separated on-memory list that contains the primary keys (Long numbers) of all objects. I need to add/remove keys from the list when object is added / removed from database. I'm using an ArrayList right now but I'm afraid ArrayList would not suit it when the number of records grows. (Imagine you have to iterate over several hundred thousands of elements every time an object is removed from database). Back to the time when I did .NET programming, then I would use a sorted List (List is a .NET class that once Sorted property set to true, will maintain order of its element, and provide binary search that help remove/insert element very quick). I'm hoping that I can find some thing similar from java BCL but unluckily, I didn't find a good match.

Answer 1

GlazedLists has a very, very good sorted list implementation

Answer 2

What about using a HashMap? Insertion, deletion, and retrieval are all O(1) operations. If you wanted to sort everything, you could grab a List of the values in the Map and run them through an O(n log n) sorting algorithm.

edit

A quick search has found LinkedHashMap, which maintains insertion order of your keys. It's not an exact solution, but it's pretty close.

Answer 3

Depending on how you're using the list, it may be worth it to use a TreeSet and then use the toArray() method at the end. I had a case where I needed a sorted list, and I found that the TreeSet + toArray() was much faster than adding to an array and merge sorting at the end.

Answer 4

Phuong:

Sorting 40,000 random numbers:

0.022 seconds

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;


public class test
{
    public static void main(String[] args)
    {
        List<Integer> nums = new ArrayList<Integer>();
        Random rand = new Random();
        for( int i = 0; i < 40000; i++ )
        {
            nums.add( rand.nextInt(Integer.MAX_VALUE) );
        }

        long start = System.nanoTime();
        Collections.sort(nums);
        long end = System.nanoTime();

        System.out.println((end-start)/1e9);
    }
}   

Since you rarely need sorting, as per your problem statement, this is probably more efficient than it needs to be.

Answer 5

It seems that you want a list structure with very fast removal and random access by index (not by key) times. An ArrayList gives you the later and a HashMap or TreeMap give you the former.

There is one structure in Apache commons collections that may be what you are looking for, the TreeList. The JavaDoc specifies that it is optimized for quick insertion and removal at any index in the list. If you also need generics though, this will not help you.