Как ArrayList расширяется динамически

Как ArrayList расширяется динамически

Основная идея

ArrayList в Java — это обёртка над обычным массивом. Когда массив переполняется, ArrayList создаёт новый, большего размера, и копирует туда старые данные. Это происходит автоматически и прозрачно для пользователя.

Внутренняя структура

public class ArrayList<E> extends AbstractList<E> implements List<E> {
    // Внутренний массив (по умолчанию пустой)
    transient Object[] elementData;
    
    // Текущее количество элементов
    private int size;
    
    // Конструктор: создаёт пустой ArrayList
    public ArrayList() {
        this.elementData = new Object[0]; // Пустой массив
    }
    
    // Конструктор с начальной ёмкостью
    public ArrayList(int initialCapacity) {
        this.elementData = new Object[initialCapacity];
    }
}

Процесс расширения

Шаг 1: Добавление первого элемента

ArrayList<String> list = new ArrayList<>();
// elementData.length = 0, size = 0

list.add("Hello");
// 1. Проверка: size (0) + 1 > elementData.length (0)? YES → нужно расширить
// 2. Расчёт новой ёмкости: 0 → 1
// 3. Создание нового массива размером 1
// 4. Копирование старых данных (нет)
// 5. Добавление нового элемента
// elementData = ["Hello"], size = 1, capacity = 1

Шаг 2: Добавление второго элемента

list.add("World");
// 1. Проверка: size (1) + 1 > capacity (1)? YES → расширить
// 2. Новая ёмкость: calculateCapacity(1 + 1) = 1 → 2  // Увеличение в 1.5 раза
// 3. Создание нового массива размером 2
// 4. Копирование: ["Hello"] → новый массив → ["Hello", ?, ?]
// 5. Добавление: ["Hello", "World"]
// elementData.length = 2, size = 2

Шаг 3-10: Добавление 9 элементов

Добавление 3-го:
  size (2) + 1 > capacity (2)? YES
  Новая ёмкость: 2 → 3
  elementData = ["Hello", "World", "!", ?, ?]
  size = 3, capacity = 3

Добавление 4-го:
  size (3) + 1 > capacity (3)? YES
  Новая ёмкость: 3 → 4 (4 = 3 * 1.5 = 4.5 → int)
  size = 4, capacity = 4

Добавление 5-го:
  size (4) + 1 > capacity (4)? YES
  Новая ёмкость: 4 → 6 (6 = 4 * 1.5 = 6)
  size = 5, capacity = 6

... и так далее

Алгоритм расширения (grow)

В Java 8+ алгоритм:

private void grow(int minCapacity) {
    // Старая ёмкость
    int oldCapacity = elementData.length;
    
    // Новая ёмкость = старая * 1.5 (на самом деле: oldCapacity >> 1 = oldCapacity / 2)
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    
    // Если даже это мало, используем minCapacity
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    
    // Предел: Integer.MAX_VALUE - 8
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    
    // Создание нового массива и копирование данных
    elementData = Arrays.copyOf(elementData, newCapacity);
}

Расширение на 50% каждый раз:

Capacity: 1 → 2 → 3 → 4 → 6 → 9 → 13 → 19 → 28 → 42 → 63 → ...
                (1.5x)

На практике: примеры

public class ArrayListGrowthExample {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        
        // Добавляем 100 элементов и смотрим рост
        for (int i = 1; i <= 100; i++) {
            list.add(i);
            
            // Способ 1: Рефлексия (не рекомендуется в продакшене)
            if (i == 1 || i == 2 || i == 3 || i == 5 || i == 10 || i == 50) {
                int capacity = getCapacity(list);
                System.out.printf("size=%3d, capacity=%3d%n", list.size(), capacity);
            }
        }
        
        // Вывод:
        // size=  1, capacity=  1
        // size=  2, capacity=  2
        // size=  3, capacity=  3
        // size=  5, capacity=  6
        // size= 10, capacity= 15
        // size= 50, capacity= 75
    }
    
    static int getCapacity(ArrayList<?> list) {
        try {
            java.lang.reflect.Field field = ArrayList.class.getDeclaredField("elementData");
            field.setAccessible(true);
            Object[] elementData = (Object[]) field.get(list);
            return elementData.length;
        } catch (Exception e) {
            return -1;
        }
    }
}

Копирование данных: System.arraycopy()

Когда ArrayList расширяется, использует встроенный метод C:

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    
    // Это копирует данные из старого массива в новый
    elementData = Arrays.copyOf(elementData, newCapacity);
    
    // Arrays.copyOf() внутри использует:
    // System.arraycopy(oldArray, 0, newArray, 0, oldArray.length);
}

Сложность: O(n), где n — количество существующих элементов.

Амортизированная сложность

Добавление в ArrayList выглядит как O(1), но на самом деле:

Первые 100 добавлений:
- 99 добавлений: O(1)
- 1 добавление (когда полный): O(n) — копирование

Итого: (99 * 1 + 1 * 100) / 100 = 199 / 100 ≈ O(1) в среднем

Это называется АМОРТИЗИРОВАННАЯ СЛОЖНОСТЬ O(1)

Оптимизация: capacityTrimToSize

Если добавили 1000 элементов, но потом удалили 900, ArrayList всё ещё держит ёмкость 1000:

ArrayList<String> list = new ArrayList<>();
for (int i = 0; i < 1000; i++) {
    list.add("item" + i);
}

// Удаляем 900 элементов
for (int i = 0; i < 900; i++) {
    list.remove(0);
}

// size = 100, но capacity = 1000 (памяти занимает много!)
System.out.println("Size: " + list.size()); // 100

// Решение: сжать к реальному размеру
list.trimToSize(); // capacity = 100

LinkedList: альтернатива

Если много удалений/вставок в начало:

// ❌ LinkedList медленнее для поиска
LinkedList<String> list = new LinkedList<>(); // Не нужна пред-аллокация
list.add("Hello");    // O(1) — просто добавляем узел
list.remove(0);       // O(1) — удаляем узел
list.get(0);          // O(n) — нужно пройти с начала

// ✅ ArrayList быстрее для поиска
ArrayList<String> list = new ArrayList<>();
list.add("Hello");    // O(1) амортизированная
list.remove(0);       // O(n) — нужно сдвинуть остальные
list.get(0);          // O(1) — прямой доступ по индексу

Инициализация с известным размером

// ❌ Плохо: будет много расширений
ArrayList<String> list = new ArrayList<>();
for (int i = 0; i < 1000000; i++) {
    list.add("item" + i); // Расширяется много раз
}

// ✅ Хорошо: одна аллокация
ArrayList<String> list = new ArrayList<>(1000000);
for (int i = 0; i < 1000000; i++) {
    list.add("item" + i); // Просто добавляет
}

// Профит: избегаем многократного копирования данных

Итого: работа ArrayList

1. Начало: пустой массив (длина 0)
2. Первое добавление: расширение → массив длины 1
3. Последующие: каждое переполнение → увеличение на 50% + копирование
4. Сложность добавления: O(1) амортизированная (не O(n)!)
5. Удаление в начало: O(n), так как нужно сдвинуть элементы
6. Поиск: O(n) в худшем случае (но O(1) по индексу)

ArrayList оптимален для приложений, где нужны частые чтения и редкие вставки/удаления в конец.