Насколько увеличится размер ArrayList при вставке

# Как увеличивается размер ArrayList при вставке

ArrayList имеет два параметра: size (количество элементов) и capacity (вместимость массива).

Поведение при вставке

Size увеличивается всегда на 1

ArrayList<String> list = new ArrayList<>();
list.add("A");  // size = 1
list.add("B");  // size = 2
// size увеличивается для каждого add

Capacity растёт только при необходимости

Начальная вместимость: 10 элементов

Добавляем 10 элементов:
- size = 10, capacity = 10 (полно)

Добавляем 11-й элемент:
- Capacity НЕ достаточна
- Создаётся новый массив
- capacity = 10 + (10 >> 1) = 15
- size = 11, capacity = 15

Добавляем с 12 по 15 элемент:
- size = 15, capacity = 15 (полно)

Добавляем 16-й элемент:
- capacity = 15 + (15 >> 1) = 22
- size = 16, capacity = 22

Формула роста

new_capacity = old_capacity + (old_capacity >> 1);
// >> 1 означает деление на 2
// Т.е. увеличение на 50% (умножение на 1.5)

Примеры:
10 → 15
15 → 22
22 → 33
33 → 49

Код ArrayList

private void ensureCapacityInternal(int minCapacity) {
    if (minCapacity - elementData.length > 0) {
        grow(minCapacity);
    }
}

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);  // Увеличение на 50%
    
    if (newCapacity - minCapacity < 0) {
        newCapacity = minCapacity;
    }
    
    elementData = Arrays.copyOf(elementData, newCapacity);
}

Пример в коде

ArrayList<Integer> list = new ArrayList<>();

for (int i = 0; i < 20; i++) {
    list.add(i);
    // Распечатаем размер (size) и вместимость (capacity)
    int capacity = getCapacity(list);  // Это приватное поле
    System.out.println("Size: " + (i + 1) + ", Capacity: " + capacity);
}

// Вывод:
// Size: 1, Capacity: 10  (начальное)
// Size: 2, Capacity: 10
// ...
// Size: 10, Capacity: 10 (полно)
// Size: 11, Capacity: 15 (увеличилось на 50%)
// Size: 12, Capacity: 15
// ...
// Size: 15, Capacity: 15 (полно)
// Size: 16, Capacity: 22 (увеличилось)
// Size: 17, Capacity: 22
// ...
// Size: 20, Capacity: 22

Получить вместимость (реальный код)

public static int getArrayListCapacity(ArrayList<?> list) {
    try {
        Field field = ArrayList.class.getDeclaredField("elementData");
        field.setAccessible(true);
        Object[] data = (Object[]) field.get(list);
        return data.length;
    } catch (NoSuchFieldException | IllegalAccessException e) {
        throw new RuntimeException(e);
    }
}

// Использование
ArrayList<String> list = new ArrayList<>();
list.add("A");
int cap = getArrayListCapacity(list);  // 10

Когда используется больший размер

ArrayList<String> list = new ArrayList<>(3);
// Capacity = 3 (указана явно)

list.add("A");  // size = 1, capacity = 3
list.add("B");  // size = 2, capacity = 3
list.add("C");  // size = 3, capacity = 3 (полно)
list.add("D");  // size = 4, capacity = 3 + (3 >> 1) = 4

Важно:

• Size: видимое количество элементов
• Capacity: внутренний размер массива
• Capacity НЕ УМЕНЬШАЕТСЯ при удалении
• Capacity растёт на 50% каждый раз
• Это амортизированно O(1) добавление