Что знаешь про класс, реализующий динамический массив в Java

Динамические массивы в Java: ArrayList

В Java динамический массив реализован классом ArrayList, находящимся в пакете java.util. Это один из самых часто используемых классов коллекций, и его глубокое понимание критично для разработчика.

Основные характеристики

ArrayList — это изменяемая коллекция, которая автоматически растёт по мере добавления элементов. На отличие от обычного массива, она:

• Позволяет добавлять и удалять элементы без переопределения размера
• Использует обобщения (generics) для типизации
• Реализует интерфейсы List, Collection, Iterable и Cloneable
• Не является thread-safe (не синхронизирована)

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

private static final int DEFAULT_CAPACITY = 10;
private Object[] elementData;
private int size;

Внутри ArrayList использует обычный массив Object[]. Когда массив заполняется, происходит:

1. Выделение новой памяти — создаётся новый массив большего размера
2. Копирование данных — элементы из старого массива копируются в новый
3. Удаление старого массива — сборщик мусора освобождает память

Увеличение ёмкости

По умолчанию ArrayList стартует с ёмкостью 10 элементов. Когда лимит достигнут, ёмкость увеличивается по формуле:

newCapacity = oldCapacity + (oldCapacity >> 1)  // увеличение на 50%

Пример:

• Начальная ёмкость: 10
• После заполнения: 15 (10 + 10/2)
• Далее: 22 (15 + 15/2)
• И так далее...

Этой алгоритм называется exponential growth и обеспечивает amortized O(1) для операции add().

Основные операции

Создание:

// С типом
ArrayList<String> list = new ArrayList<>();

// С начальной ёмкостью
ArrayList<Integer> numbers = new ArrayList<>(100);

// Инициализация с другой коллекции
ArrayList<String> copy = new ArrayList<>(anotherList);

Добавление элементов:

list.add("Java");           // O(1) amortized, O(n) в худшем случае
list.add(0, "Python");      // O(n) — нужно сдвинуть элементы
list.addAll(otherList);     // O(n + m)

Доступ к элементам:

String first = list.get(0);     // O(1) — прямой доступ
int index = list.indexOf("Java"); // O(n)

Удаление:

list.remove(0);              // O(n) — нужно сдвинуть элементы
list.remove("Java");         // O(n)
list.clear();                // O(n)

Сложность операций

Особенности и подводные камни

1. Примитивные типы

ArrayList работает только с объектами, но Java использует autoboxing:

ArrayList<Integer> nums = new ArrayList<>();
nums.add(5);              // Автоматически конвертируется в Integer
int value = nums.get(0);  // Автоматически распаковывается

Это удобно, но может привести к NullPointerException при распаковке null.

2. Не потокобезопасность

// Это может привести к проблемам в многопоточной среде
ArrayList<String> list = new ArrayList<>();
// Для многопоточности используй:
List<String> syncList = Collections.synchronizedList(new ArrayList<>());

3. Итерация и модификация

// ОШИБКА: ConcurrentModificationException
for (String s : list) {
    if (s.equals("remove_me")) {
        list.remove(s);  // Нарушение итератора
    }
}

// ПРАВИЛЬНО: используй Iterator
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().equals("remove_me")) {
        it.remove();  // Безопасное удаление
    }
}

4. Клонирование

ArrayList<String> original = new ArrayList<>();
original.add("Java");

// ПОВЕРХНОСТНОЕ копирование (shallow copy)
ArrayList<String> copy1 = (ArrayList<String>) original.clone();

// ГЛУБОКОЕ копирование (deep copy)
ArrayList<String> copy2 = new ArrayList<>(original);

// Для действительно глубокого копирования объектов:
ArrayList<String> copy3 = original.stream()
    .collect(Collectors.toCollection(ArrayList::new));

Когда использовать ArrayList

Используй ArrayList:

• Когда нужны частые вставки/удаления в конец
• Когда требуется произвольный доступ к элементам
• Когда размер коллекции часто меняется

Не используй ArrayList:

• Для частых вставок/удалений в начало или середину (используй LinkedList)
• Когда нужна потокобезопасность (используй CopyOnWriteArrayList или Collections.synchronizedList())
• Когда размер известен и статичен (используй обычный массив)

Современный синтаксис Java 9+

// List.of() создаёт неизменяемый список
List<String> fixed = List.of("a", "b", "c");

// Чтобы сделать его изменяемым:
ArrayList<String> mutable = new ArrayList<>(fixed);

Владение ArrayList — один из краеугольных камней Java-разработки, и глубокое понимание его внутреннего механизма отличает опытного разработчика от новичка.