Каков механизм добавления элементов в ArrayList?

Сначала разберемся, какими способами можно увеличить ArrayList.

1) с помощью метода add(T element)
2) с помощью метода add(int index, T element)
3) с помощью метода addAll(Collection<? extends T> c)
4) с помощью метода addAll(int index, Collection<? extends T> c)

Разберем каждый из способов отдельно:

1) Вот исходный код метода add(T element):

public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

Он увеличивает переменную modCount(количество структурных преобразований). Вот выдержка из javadoc 1.4:

Это поле используется iteratorом и выполняет реализацию iteratorа, возвращаемого методами iteratorа и listIterator. Если значение этого поля неожиданно изменяется, iterator (или iterator списка) будет вызывать исключение ConcurrentModificationException в ответ на следующие действия: удаление, предыдущее, задание или добавление. Это обеспечивает отказоустойчивое поведение, а не недетерминированное поведение перед лицом одновременной модификации во время итерации.

Затем вызывает метод add(E e, Object[], int s). А после возвращает true, так как он должен это значение возвращать, так как так указано в Collection.add(E e).

Разберем этот метод add(E e, Object[] elementData, int s). Вот исходный код:

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

В переменной e - наш создаваемый элемент. В переменной elementData - массив всех элементов(может быть не полностью заполнен), и s - количество реально располагающихся в массиве элементов элементов. Если массив заполнится не полностью - добавляем элемент в массив и увеличиваем переменную, содержащую количество реально располагающихся элементов. Иначе - помимо этого предварительно увеличиваем размер массива с помощью метода grow().

Разберем этот метод grow(). Вот исходный код:

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

Значит, он лишь вызывает другой метод grow, но уже с параметром int minCapacity, в который мы помещаем значение переменной, содержащей количество реально располагающихся элементов, увеличенное на единицу. Вот и его исходный код:

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity, /* minimum growth */
                oldCapacity >> 1           /* preferred growth */);
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

Если массив не пуст, то мы увеличиваем наш исходный массив на длину, равную половине(округление вниз) старой длины, если получившаяся длина не больше максимальной длины массива(Integer.MAX_VALUE - 8), иначе равную максимальной длине массива, если oldLength + minGrowth меньше максимальной длины массива, иначе равную Integer.MAX_VALUE.
Иначе мы заново инициализируем массив, передавая в него ссылку на массив объектов длиной 10 или minCapacity, если minCapacity > 10.
Если кого интересует код ArraysSupport.newLength, вот исходники(из java 13 только нашел):

public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
    // assert oldLength >= 0
    // assert minGrowth > 0
    int newLength = Math.max(minGrowth, prefGrowth) + oldLength;
    if (newLength - MAX_ARRAY_LENGTH <= 0) {
        return newLength;
    }
    return hugeLength(oldLength, minGrowth);
}
private static int hugeLength(int oldLength, int minGrowth) {
    int minLength = oldLength + minGrowth;
    if (minLength < 0) { // overflow
        throw new OutOfMemoryError("Required array length too large");
    }
    if (minLength <= MAX_ARRAY_LENGTH) {
        return MAX_ARRAY_LENGTH;
    }
    return Integer.MAX_VALUE;
}

Разбор метода add(T element) окончен.

2) Вот исходный код метода add(int index, T element):

public void add(int index, E element) {
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow();
    System.arraycopy(elementData, index,
                     elementData, index + 1,
                     s - index);
    elementData[index] = element;
    size = s + 1;
}

rangeCheckForAdd(int index) кидает ошибку, если index не входит в число реальных элементов. modCount традиционно увеличивается. Затем увеличиваем длину массива с помощью метода grow(), если места для нового элемента нет, и сдвигаем все элементы, находящиеся справа от индекса, куда нужно вставить элемент, вправо, вставляя в образовавшееся "пустое пространство" объект, который нужно вставить. Внутренняя переменная длины традиционно увеличивается.

3) Вот исходный код метода addAll(Collection<? extends T> c):

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    modCount++;
    int numNew = a.length;
    if (numNew == 0)
        return false;
    Object[] elementData;
    final int s;
    if (numNew > (elementData = this.elementData).length - (s = size))
        elementData = grow(s + numNew);
    System.arraycopy(a, 0, elementData, s, numNew);
    size = s + numNew;
    return true;
}

modCount традиционно увеличивается. Получаем массив из коллекции, чтобы можно было совершить вставку массива с помощью стандартного метода. Если коллекция, которую необходимо вставить, пуста, то возвращаем false. Если вставляемая коллекция не вмещается в массив - увеличиваем его. Затем добавляем "коллекцию" в самый конец массива. Внутренняя переменная длины традиционно увеличивается. Рапортуем о удачном выполнении работы.

4) Вот исходный код метода addAll(int index, Collection<? extends T> c):

public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);
    Object[] a = c.toArray();
    modCount++;
    int numNew = a.length;
    if (numNew == 0)
        return false;
    Object[] elementData;
    final int s;
    if (numNew > (elementData = this.elementData).length - (s = size))
        elementData = grow(s + numNew);
    int numMoved = s - index;
    if (numMoved > 0)
        System.arraycopy(elementData, index,
                         elementData, index + numNew,
                         numMoved);
    System.arraycopy(a, 0, elementData, index, numNew);
    size = s + numNew;
    return true;
}

rangeCheckForAdd(int index) выполняет ту же функцию, что и при вставке одиночного элемента. Выполняем все то же, что и в addAll(Collection<? extends T> c), до строчки с созданием переменной numMoved, в которую записывается количество реальных элементов массива, следующих после index включительно(помните, что итерация начинается с 0!). Если они вообще есть, то перемещаем их направо, освобождая место для вставляемой коллекции. Затем производится вставка коллекции в диапазон, начинающийся с index. Внутренняя переменная длины традиционно увеличивается. Рапортуем о удачном выполнении работы.

Спасибо за внимание. Если заметили ошибку или неточность - скажите о ней, готов принять любую критику.