Which data type should I choose for a sequence of sorted integers?

Question

I have a a row of int numbers, e.g. 1 2 3 7 8 9. They are sorted.

I often need to insert numbers in this row, so that the row stays sorted, e.g. 4 => 1 2 3 4 7 8 9. Sometimes I have to read the row from the start to a number, that depends on the numbers in the row.

Which data type to choose best and how to insert the new number best?

Answer 1

If your sequence does not have repetitions you can use a SortedSet<Integer>, say, a TreeSet<Integer>, so that every time you and an element the sequence will remain sorted.

If the sequence does have repetitions check out Guava's sorted multiset.

Answer 2

try ArrayList. it is much easier to manipulate than a simple array. if you need to only work with primitives, this can still be done with an array of ints.

ArrayList<Integer> foo = new ArrayList<integer>;
foo.add(2,4) //puts a 4 at index 2, shifting everything else down