Is there a list implementation that would allow gaps?

Question

I'm looking for a collection that would be some sort of a list that allows gaps. The objectives are:

• every element has some index in the collection that is meaningful.
• the collection is to be sparse and not continuous; its size should return the number of proper elements, hence the workaround of initializing with null wouldn't work.
• subList method is desirable to access sublists according to index intervals

Sample use case:

List<Integer> list = /* ? */;
list.add(0,5);
list.add(1,4);
list.add(5,3);
for( Integer i : list )
{
    System.out.print( i + " " );
}
/* desired output : "5 4 3 "*/

Answer 1

You may use a Map and only set the keys you need.

You can keep the insertion order if you want, take a look: Java Class that implements Map and keeps insertion order

Answer 2

Use a Map<Integer,Integer>. The key would be your index and the value the value of the list.

For your subList requirement, perhaps TreeMap<Integer,Integer> would work, as it keeps the keys sorted and makes it easy to iterate over a sub-list.

Of course this means you can't use the List interface. If you must use the List interface, you can make your own List implementation backed by a TreeMap (for example, list.add(5,3) would call map.put(5,3)).