Back to basics : anatomy of an ArrayList

The ArrayList is ubiquitous in Java programming and is often picked as the default List implementation. Is this always a good choice ? Let’s take a peek at the source code for some of the key methods of ArrayList.java and find out.

Data structure

As the name implies an ArrayList is backed by an array, no surprises here.

Object[] elementData


To retrieve an element:

public E get(int index) {
   rangeCheck(index);
   return (E) elementData[index];
}

Pretty straightforward – check that the index parameter is valid and return the element located at this index. Because all elements are stored as Objects a cast from Object to the type parameter of the ArrayList is required beforehand.

To add an element:

public boolean add(E e) {
   ensureCapacityInternal(size + 1);
   elementData[size++] = e;
   return true;
}

First check that the array is large enough to accomodate the new element (if not grow the array). Then add the element at the end of the array. Growing the array involves calculating a new capacity and copying the existing array into an array of bigger capacity, an expensive operation:

elementData = Arrays.copyOf(elementData, newCapacity);

The more elements in the array the more expensive the copy will get.

To remove an element

Removing is another potentially expensive operation as another array copy is required (unless the element removed happens to be the last element of the array). An element is removed by taking all the elements on its right hand side and copying them in place of where this element used to be.

public E remove(int index) {
rangeCheck(index);

modCount++;
E oldValue = elementData(index);

int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // Let gc do its work

return oldValue;
}

Note the increment of the modCount variable above. This variable is written to by any operation which structurally changes the content of the list (ie. add, remove, clear…). And it is read by methods iterating upon the content of the list to detect wether any structural changes occurred. If that’s the case then the iteration may yield incorrect results and a ConcurrentModificationException is thrown.

In Summary:

An arrayList ideal use case is when the number of structural operations is kept to a minimum, because 1) they dont scale and 2) they might raise an concurrentModification exception.

point 1) can be adressed by swapping an ArrayList for a LinkedList… faster structural operations, but much slower retrievals.

point 2) can be remediated by using a CopyOnWriteArrayList instead. The tradeoff in this case is that any write operations (structurally or otherwise) will involve an array copy and therefore impact performance.

Advertisements

2 thoughts on “Back to basics : anatomy of an ArrayList

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s