Какие знаешь случаи, когда сложность добавления элемента в конец ArrayList равна O(n)?

Когда add() в ArrayList имеет сложность O(n)

Обычно добавление элемента в конец ArrayList имеет амортизированную сложность O(1), но есть несколько случаев, когда операция деградирует до O(n).

1. Переполнение вместимости (Capacity Resize)

Основной случай — когда внутренний массив переполняется:

val list = ArrayList<Int>()
list.add(1)  // O(1) — есть место
list.add(2)  // O(1) — есть место
list.add(3)  // O(n)! — нет места, нужна пересаливание массива

Когда в ArrayList нет свободного места, он:

1. Создаёт новый массив большего размера (обычно в 1.5 раза)
2. Копирует все элементы из старого массива в новый (O(n))
3. Добавляет новый элемент

Внутренняя реализация:

private fun ensureCapacity(minCapacity: Int) {
    if (minCapacity > elementData.size) {
        val oldCapacity = elementData.size
        val newCapacity = oldCapacity + (oldCapacity shr 1)  // Увеличиваем на 50%
        val newElementData = elementData.copyOf(newCapacity)  // O(n)
        elementData = newElementData
    }
}

2. Вставка элемента в середину (insert)

Хотя это другой метод, add() можно переопределить:

val list = ArrayList<Int>()
list.add(1)
list.add(2)
list.add(3)
list.add(1, 99)  // Вставка в позицию 1 — O(n)

При вставке в позицию i нужно сдвинуть все элементы с индекса i до конца, что требует O(n) операций сдвига.

3. Множественные добавления при малой начальной ёмкости

Если создать ArrayList с маленькой начальной ёмкостью и добавить много элементов:

val list = ArrayList<Int>(1)  // Ёмкость = 1
for (i in 0 until 1000000) {
    list.add(i)  // Каждое добавление может быть O(n)
}

При каждом переполнении происходит копирование O(n), что в сумме даёт O(n²) для всех операций.

4. Добавление элемента с trim операцией

Если применить trimToSize(), а потом добавлять элемент:

val list = ArrayList<Int>()
for (i in 0 until 10) list.add(i)

list.trimToSize()  // Сокращаем capacity к размеру элементов
list.add(100)      // O(n) — нужна пересаливание

После trimToSize() вместимость точно равна количеству элементов, поэтому следующее добавление гарантированно вызовет реаллокацию.

5. Использование в многопоточной среде без синхронизации

При работе с ArrayList из нескольких потоков одновременно:

// Небезопасно!
val list = ArrayList<Int>()
Thread {
    list.add(1)  // Может быть O(n) из-за race condition
}.start()
Thread {
    list.add(2)  // Может быть O(n)
}.start()

Внутреннее состояние может быть нарушено, что приведёт к неопределённому поведению и дополнительным операциям переаллокации.

6. При работе с большими объектами

Если элементы — это большие объекты, копирование при пересаливании может быть очень затратным:

data class LargeObject(val data: ByteArray) // 1MB

val list = ArrayList<LargeObject>(1)
for (i in 0 until 100) {
    list.add(LargeObject(ByteArray(1024 * 1024)))  // O(n) копирование
}

Хотя количество операций O(n), время выполнения может быть огромным из-за размера данных.

7. Граничные случаи с Integer.MAX_VALUE

При добавлении к очень большому ArrayList:

// ArrayList с миллионами элементов
val list = ArrayList<Int>(Integer.MAX_VALUE / 2)
for (i in 0 until 1000000) {
    list.add(i)  // В какой-то момент произойдёт реаллокация
}

Best Practices для избежания O(n) добавления

• Инициализируйте с правильной ёмкостью:

val list = ArrayList<Int>(expectedSize)  // Лучше O(1)

• Не используйте add(int index, E element) в цикле (это O(n²))
• Для частых вставок в начало используйте LinkedList (O(1) для add/remove в начале)
• Избегайте trimToSize() перед добавлением элементов
• Предварительно выделяйте место:

list.ensureCapacity(expectedSize)

Выводы

Основной случай O(n) при добавлении в конец ArrayList — это переполнение внутреннего массива и необходимость его переаллокации с копированием всех элементов. На практике это редко происходит благодаря амортизированному анализу, но нужно понимать этот механизм для оптимизации критичного по производительности кода.