Что будет при добавлении в Arraylist 11 элемента, при заданных 10 элементах?

Что происходит при добавлении 11-го элемента в ArrayList с 10 элементами

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

Краткий ответ

При добавлении 11-го элемента в ArrayList с 10 элементами произойдет увеличение внутреннего массива (resize). Старый массив размера 10 будет скопирован в новый массив размера 15 (или другого размера, зависит от реализации), и затем добавится новый элемент.

Как это работает внутри

Инициализация ArrayList

ArrayList<Integer> list = new ArrayList<>();
// Начальная вместимость (capacity): 10

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

// Внутренне это примерно:
private Object[] elementData = new Object[10]; // начальная вместимость
private int size = 0; // количество элементов

Добавление первых 10 элементов

for (int i = 0; i < 10; i++) {
    list.add(i); // size увеличивается с 0 до 10
}

// После этого:
// elementData.length = 10 (вместимость)
// size = 10 (реальное количество элементов)

Добавление 11-го элемента: происходит resize

list.add(10); // Пытаемся добавить 11-й элемент

// ArrayList проверяет: size (10) + 1 > elementData.length (10)?
// ДА! Нужно расширить массив

// Новая вместимость вычисляется:
newCapacity = oldCapacity + (oldCapacity >> 1);
//           = 10 + (10 >> 1)
//           = 10 + 5 = 15

// Создается новый массив и копируются старые элементы
Object[] newElementData = new Object[15];
System.arraycopy(elementData, 0, newElementData, 0, 10);
elementData = newElementData; // ссылка обновляется

// Теперь добавляется новый элемент
elementData[10] = 10;
size = 11;

Коэффициент расширения

Формула: 1.5x от старого размера

Staraya emkost:     10
Novaya emkost:      10 + (10 >> 1) = 15
Na sleduushiy:      15 + (15 >> 1) = 22
Posle togo:         22 + (22 >> 1) = 33

Это лучше, чем расширять на 1 элемент каждый раз (было бы O(n²)), и лучше, чем на 2x (меньше неиспользуемой памяти).

Визуализация

ДО добавления 11-го элемента:
┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
│0│1│2│3│4│5│6│7│8│9│  <- 10 элементов
└─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
^                     ^
size=10         capacity=10

ПОСЛЕ добавления 11-го элемента:
┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬──┬──┬──┬──┬──┐
│0│1│2│3│4│5│6│7│8│9│10│ │ │ │ │  <- 15 элементов место
└─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴──┴──┴──┴──┴──┘
^                    ^
size=11        capacity=15
        (старый массив скопирован,
         добавлен новый элемент)

Исходный код ArrayList (упрощено)

public class ArrayList<E> {
    private static final int DEFAULT_CAPACITY = 10;
    private Object[] elementData;
    private int size;
    
    public ArrayList() {
        this.elementData = new Object[DEFAULT_CAPACITY];
        this.size = 0;
    }
    
    public boolean add(E e) {
        // Проверка вместимости
        ensureCapacityInternal(size + 1);
        
        // Добавление элемента
        elementData[size++] = e;
        return true;
    }
    
    private void ensureCapacityInternal(int minCapacity) {
        if (minCapacity - elementData.length > 0) {
            grow(minCapacity);
        }
    }
    
    private void grow(int minCapacity) {
        // Вычисляем новую вместимость (1.5x)
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1); // oldCapacity * 1.5
        
        if (newCapacity - minCapacity < 0) {
            newCapacity = minCapacity;
        }
        
        // Копируем элементы в новый массив
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

Производительность: анализ сложности

Время добавления элемента:

При добавлении 1-10 элементов: O(1) - просто добавляешь
При добавлении 11 элемента: O(n) - нужно скопировать все 10 старых элементов
При добавлении 12-15 элементов: O(1) - есть место
При добавлении 16 элемента: O(n) - опять resize (15+7 = 22)

Амортизированная сложность: O(1)

Хотя некоторые добавления O(n), в среднем это O(1), потому что resize происходит редко:

Добавляем элементы:
1,2,3,4,5,6,7,8,9,10 - все O(1), 1 раз инициализация O(10)
11 - O(10) resize, затем O(1)
12-15 - O(1)
16 - O(15) resize, затем O(1)
17-22 - O(1)
23 - O(22) resize

А что за Итого за 100 добавлений?
Примерно 10 + 15 + 22 + ... ≈ O(n) операций за n добавлений
=> O(n) / n = O(1) в среднем

Сравнение с LinkedList

                    ArrayList       LinkedList
─────────────────────────────────────────────────
Добавление в конец     O(1)*           O(1)
Добавление в начало    O(n)            O(1)
Удаление из конца      O(1)*           O(1)
Удаление из начала     O(n)            O(1)
Удаление из середины   O(n)            O(n)
Поиск по индексу       O(1)            O(n)
Поиск элемента        O(n)            O(n)
Память               Экономно     Расходно (links)

* amortized

Практические примеры

Прообразитель ArrayListа — массив

int[] arr = new int[10]; // фиксированный размер
// Если нужно 11 элементов, нужно создавать новый массив
int[] newArr = new int[15];
System.arraycopy(arr, 0, newArr, 0, 10);
arr = newArr;

// ArrayList делает это автоматически
ArrayList<Integer> list = new ArrayList<>(10);
list.add(11); // все происходит внутри

Если знаешь заранее размер

// Плохо: много resize операций
ArrayList<Integer> list = new ArrayList<>(); // capacity = 10
for (int i = 0; i < 1_000_000; i++) {
    list.add(i); // каждое resize копирует все элементы
}

// Хорошо: указываешь нужный размер
ArrayList<Integer> list = new ArrayList<>(1_000_000); // capacity = 1_000_000
for (int i = 0; i < 1_000_000; i++) {
    list.add(i); // только добавляет, без resize
}

Изменения в Java 8+

В Java 8 формула расширения немного изменилась:

// Java 7 и ранее
int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5x

// Java 8+
int newCapacity = hugeCapacity(minCapacity);
// Проверка на Integer.MAX_VALUE overflow

Но общий принцип остался: 1.5x расширение.

На собеседовании

Полный ответ выглядит так:

"ArrayList использует внутренний массив. Когда мы добавляем 11-й элемент при размере 10, происходит следующее:

1. ArrayList проверяет, хватает ли места в массиве
2. Места не хватает, поэтому создается новый массив размером 15 (используется формула: newCapacity = oldCapacity + (oldCapacity >> 1))
3. Все 10 старых элементов копируются в новый массив (System.arraycopy)
4. 11-й элемент добавляется в новый массив
5. Ссылка elementData обновляется на новый массив

Время операции resize: O(n), но амортизированная сложность добавления остается O(1)."

Вывод

Это важно понимать потому что:

1. Производительность: если добавляешь много элементов, инициализируй с нужным размером
2. Выбор структуры: ArrayList хорош для доступа по индексу, LinkedList — для частого добавления/удаления
3. Память: ArrayList может быть больше, чем нужно (capacity > size)
4. Амортизированная сложность: важный концепт в анализе алгоритмов