Java ArrayList add operations in concept

As a new core Java developer who develops a low latency trading system, I need to understand low-level Java. In Java, ArrayList is very commonly used for the alternative of the array. In this article, we will discuss and analyse the concept and the logic behind the screens, in a low-level way.

1. Class member

private static final int DEFAULT_CAPACITY = 10;

private static final Object[] EMPTY_ELEMENTDATA = {};

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

transient Object[] elementData; // non-private to simplify nested class access

private int size;

On the above code, the ArrayList class actually has multiple class members. The base of the ArrayList is an Object array called elementData. Moreover, the class initialize EMPTY_ELEMENTDATA and DEFAULTCAPACITY_EMPTY_ELEMENTDATA for empty ArrayList so that the JVM doesn’t need to initialize an empty array object every time and operate garbage collection. Finally, the default capacity

2. Constructor

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(Collection<? extends E> c) {
    Object[] a = c.toArray();
    if ((size = a.length) != 0) {
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else {
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
        // replace with empty array.
        elementData = EMPTY_ELEMENTDATA;
    }
}
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

The ArrayList class use the overload method to have multiple constructors so that the ArrayList class constructor can accept different parameters. The default capacity for an ArrayList should be 10, however, developers can use a custom capacity to initialize an ArrayList, or even initialize an ArrayList with a collection object.

3. Add method

public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}
private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}
private Object[] grow(int minCapacity) {
    return elementData = Arrays.copyOf(elementData,
                                       newCapacity(minCapacity));
}

private Object[] grow() {
    return grow(size + 1);
}

private int newCapacity(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity <= 0) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return minCapacity;
    }
    return (newCapacity - MAX_ARRAY_SIZE <= 0)
        ? newCapacity
        : hugeCapacity(minCapacity);
}

This is where the ArrayList magic happens. When an element is added to an ArrayList, the ArrayList will first check if the size will exceed the capacity or not. If it does, the ArrayList will call the grow() method, which will return the current capacity increased by 50% if that suffices. In this case, the time complexity of add() method in ArrayList becomes O(n) as the original base array is replaced by a new array with capacity increased by 50%.

That’s enough for the first part. In the next part, I may talk about LinkedList in Java.