Введение
ArrayList — это динамический массив в Java, реализующий интерфейс List.
Он позволяет:
- Хранить элементы в порядке
- Добавлять и удалять элементы
- Получать элемент по индексу за O(1)
- Автоматически увеличивать размер при необходимости
Внутренняя структура ArrayList
ArrayList хранит свои элементы в обычном массиве объектов:
transient Object[] elementData;
Это не ссылка на List, а простой массив Object[], выделенный в куче. Кроме массива, ArrayList хранит:
- size — текущее количество элементов
- DEFAULT_CAPACITY = 10 — начальный размер
Проверка вместимости: Как работает add(E e)
Шаг1:
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Убедиться, что хватит места
elementData[size++] = e; // Добавить элемент
return true;
}
Метод ensureCapacityInternal():
- Проверяет, хватает ли места в elementData
- Если нет — вызывает grow()
Шаг 2: Увеличение массива (grow())
private void grow() {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // увеличение на 50%
elementData = Arrays.copyOf(elementData, newCapacity);
}
Пример: Было: 10 элементов
Стало: 15 (10 + 5)
Потом: 22 → 33 → 49 → и т.д.
Операция grow() — дорогая, потому что создаётся новый массив и копируются все элементы.
Как работает get(int index)?
public E get(int index) {
rangeCheck(index); // проверка: 0 <= index < size
return (E) elementData[index];
}
Очень быстро — просто доступ по индексу → O(1)
Как работает remove(int index)?
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = (E) elementData[index];
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null; // помогаем GC
return oldValue;
}
System.arraycopy — копирует все элементы влево, чтобы заполнить дыру
→ Сложность: O(n)
Распространённые ошибки
Ошибка 1: Добавление в null-массив
ArrayList<String> list = null;
list.add("A"); // NullPointerException
Всегда инициализируйте:
ArrayList<String> list = new ArrayList<>();
Ошибка 2: Модификация во время итерации
for (String s : list) {
if (s.equals("A")) {
list.remove(s); // ConcurrentModificationException
}
}
Используйте Iterator:
Iterator<String> it = list.iterator();
while (it.hasNext()) {
if (it.next().equals("A")) {
it.remove();
}
}
Когда использовать ArrayList?
Частое чтение по индексу
✅ Да
Добавление в конец
✅ Да
Вставка/удаление в середине
❌ Нет (лучшеLinkedList)
Многопоточность
❌ Нет (используйтеCopyOnWriteArrayList)
Заключение
ArrayList — это:
- Обёртка над обычным массивом
- Динамически увеличивается при нехватке места
- Обеспечивает быстрый доступ по индексу
- Использует копирование при росте и удалении