Question about java ArrayList

[PaulStat]

Ok so you setup a new ArrayList like so

ArrayList list = new ArrayList(20);

You then add 10 items to the list, leaving it half full.

If I then do the following

listSize = list.size();

What is listSize? Is it 10 or 20?

 

[Dfhaii]

list.size() tells you how many elements there are in the collection, rather than its capacity, so in this case it'd be 10.

 

[Dj_Jestar]

I didn't think it was necessary to specify a capacity for ArrayList's as they are self growing?

 

[Energize]

I thought that was the point of them.

 

[PaulStat]

I didn't think it was necessary to specify a capacity for ArrayList's as they are self growing?

Nope not necessary but still possible

 

[Dfhaii]

I didn't think it was necessary to specify a capacity for ArrayList's as they are self growing?

That's absolutely true, they do grow if needed, but a quick look at the ArrayList (and vector) classes show why you might want to.

ArrayLists are backed by arrays, which can't have their size changed. They have a default initial capacity of 10, so the constructor will create an array with size 10 and everyone is a winner. You then add 10 objects to it and that array is full, when you then add 1 more item the ArrayList class can see that its backing array is full so it allocates a new one with double the size of the old, copies the items from the old one to the new one, sets it's reference to its backing array to the new one and adds the next item. This is fine, but when you add another 10 objects (array size is 20) it'll do the same again, and again etc.

If you know you're going to be adding a certain number of objects in one go you can set the initial size to be adequate, or use ensureCapacity which will just increase the backing array once.

ArrayList's add method:

public boolean add(E e) {
	ensureCapacity(size + 1);  // Increments modCount!!
	elementData[size++] = e;
	return true;
    }

and ensureCapacity(int Capacity)

public void ensureCapacity(int minCapacity) {
	modCount++;
	int oldCapacity = elementData.length;
	if (minCapacity > oldCapacity) {
	    Object oldData[] = elementData;
	    int newCapacity = (oldCapacity * 3)/2 + 1;
    	    if (newCapacity < minCapacity)
		newCapacity = minCapacity;
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
	}
    }

 

[Dj_Jestar]

I don't really see any issue with just leaving it to grow. Sounds a bit like preoptimisation to me, but I guess if you know it'll never, ever be more than n then specifying n won't do any harm

 

[Dfhaii]

There is no issue with leaving it to grow, just that it may be more expensive, it only really gets noticeable when adding large numbers of elements.

Example
default arraylist with size 10, we want to add 10000 elements to it size goes
10 -> 20 -> 40 -> 80 -> 160 -> 320 -> 640 ->1280 -> 2560 -> 5120 -> 10240
That's 11 different array allocations (and associated gc), and 10 copies of data from one array to another. If you created it with size 10000 or used ensureCapacity(10000) then there'd be one array alloc and no copies.

Specifying the size of it doesn't prevent any of the normal behavior though, if you set the initial size to be n and add n + 1 items it'll still happily grow as normal, so it's more a case of using it when you know the minimum number of items you'll add rather than a maximum, if you know the maximum just use an array.