Reputation: 7680

Java ArrayList add item outside current size

Wondering whether there is an efficient way to add an item to Java's ArrayList at a bigger position than its current size:

Scenario:

   ArrayList<Item> items = new ArrayList<Item>;
   ... let's say I add three elements

Now I would like to add an item at position 10 (leaving items from 3 to 10 to null)

  items.add(10,newItem);  // item.size() == 3

Is there an efficient way resizing/filling an ArrayList with nulls?

Java's implementation makes size field private :-(..

Upvotes: 7

Answers (10)

Dan

Reputation: 580

This is an older question, but you can now use SparseArray as an (almost) direct drop-in replacement for ArrayList. It allows non-contiguous integer key values, and returns null if a value has not been set for a key. Performance-wise it was designed exactly for your needs. Instead of add you use append, which is more descriptive in that you are appending to the end of whatever the max key is, even if there is gaps. You can also set at any key value you'd like, even if it is beyond the maximum key.

Upvotes: 2

Piotr Gwiazda

Reputation: 12212

@icCube- you said, that list should be about 90% full. My idea for this solution is:

If you exactly know target size - use plain array
If you are aware of target size - use ArrayList with initial capacity as close as possible to target size. Put nulls with l.addAll(Collections.nCopies(n, (String)null)); as people said.
If you don't know target size - your ArrayList will be resized many times. Resizing means copying whole underlying array (it uses Arrays.copyOf). You can imagine what happens if array is copied around - GC has lots of work. Use TreeMap then.

Upvotes: 0

Piotr Gwiazda

Reputation: 12212

Use TreeMap instead. Here is simple example to check memony consuption. Run first and second test separatly and use jvisualvm to check heap size. Remember to Perform GC several times.

    public class Test {


            public static void main(String[] args) throws InterruptedException {
                String s = "Lorem ipsum dolor sit amet, consectetur adipiscing elit. Quisque metus.";


                //Test 1
                ArrayList<String> l = new ArrayList<String>();

                for (int i = 0; i < 1000000; i++) {
                    l.add(s + " " + i);
                    l.addAll(Collections.nCopies(i % 10, (String)null)); //Add some nulls
                }
                //Heap is > 5MB

                //Test 2 uncomment and comment test 1
    //          SortedMap<Integer, String> map = new TreeMap<Integer, String>();
    //          for (int i = 0; i < 1000000; i++) {
    //              map.put(i,s + " " + i);
    //          }
                //Heap is < 5MB

                Thread.sleep(100000);

            }
    }

It looks like TreeMap version is even less memory consuming than ArrayList version. Check yourself.

Upvotes: 1

Hachi

Reputation: 3289

imho the best thing you can do is items.addAll(Collections.nCopies(6, null)) and hope, that ArrayList implements some behaviour to internally fasten this up

Upvotes: 6

rauschen

Reputation: 3996

If memory and index is so important that use a normal array.

When it becomes to small use System.arraycopy thats the way ArrayList does it internal.

Even if you use the ArrayList and have a Million Objects it is advisable to use the ArrayList(int initialCapacity)-Constructor to avoid a lot of copy-operations

Upvotes: 0

Ishtar

Reputation: 11662

How about this?

ArrayList<Item> items = new ArrayList<Item>();

items.add(new Item(0));
items.add(new Item(1));
items.add(new Item(2));

items.addAll(Collections.<Item>nCopies(7, null));
items.add(10,new Item(10));

System.out.println(items);

prints

[0, 1, 2, null, null, null, null, null, null, null, 10]

Upvotes: 2

John B

Reputation: 32949

I would consider using a SortedMap instead of a List here. This will allow for indexes to not exist:

SorteMap<Integer, Item> myMap = new TreeMap<Integer, Map>();
int i=0;
myMap.put(i++, first);
myMap.put(i++, second);
myMap.put(i++, third);
myMap.put(10, other);

If a Map truly will not work, as you stated. I would then suggest creating a Decorator around ArrayList. In the insert method, add nulls to fill the empty locations. I would suggest using Guava's ForwardingList to ease the creation of the class. This way you would only have to implement one method.

Upvotes: 0

subodh

Reputation: 6158

No, you can't do this, But if you wish to do that, then add empty object in remaining index such as..

    ArrayList<Object> items = new ArrayList<Object>();
    items.add(new Object());
    items.add(new Object());
    items.add(new Object());
    items.add(3,new Object());

Upvotes: 0