Что такое ArrayList?

Что такое ArrayList в Java?

ArrayList — это один из самых часто используемых классов в Java, представляющий собой реализацию интерфейса List на основе динамического массива. В отличие от обычного массива (int[], String[]), размер которого фиксирован после создания, ArrayList может автоматически увеличивать свою ёмкость (capacity) при добавлении новых элементов, что делает его гораздо более гибким и удобным в использовании для хранения коллекций данных, размер которых заранее неизвестен.

Ключевые характеристики ArrayList

• Динамический размер: Главное преимущество. Внутренне ArrayList хранит элементы в обычном массиве. Когда этот массив заполняется, ArrayList создаёт новый массив большего размера (обычно в 1.5 раза для стандартной реализации Java) и копирует в него все старые элементы.
• Основан на массиве: Это обеспечивает очень быстрый произвольный доступ (random access) к элементам по индексу. Операция get(int index) выполняется за константное время O(1), так как это просто обращение к элементу внутреннего массива.
• Реализует интерфейсы List, Collection, Iterable: Это означает, что ArrayList можно использовать везде, где ожидается эти интерфейсы, он поддерживает все стандартные операции с коллекциями: добавление, удаление, итерацию, поиск.
• Порядок элементов сохраняется: Элементы хранятся в той последовательности, в которой они были добавлены.
• Допускает дубликаты и null значения: В один ArrayList можно добавить несколько одинаковых объектов, а также null.
• Не является синхронизированным (not thread-safe): По умолчанию ArrayList не безопасен для использования из нескольких потоков одновременно. Если требуется потокобезопасность, необходимо использовать внешнюю синхронизацию или классы-обёртки из Collections.synchronizedList(), или выбрать CopyOnWriteArrayList, или использовать коллекции из пакета java.util.concurrent.

Основные операции и их сложность

• Добавление элемента в конец (add(E element)): O(1) в среднем случае. Если внутренний массив заполнен, происходит операция увеличения массива O(n), но она amortized (усреднённая) редко.
• Добавление элемента по индексу (add(int index, E element)): O(n). Требуется сдвиг всех элементов справа от индекса на одну позицию вправо.
• Получение элемента по индексу (get(int index)): O(1). Сильная сторона ArrayList.
• Удаление элемента по индексу (remove(int index)): O(n). Требуется сдвиг всех элементов справа от индекса на одну позицию влево.
• Поиск элемента (indexOf(Object o), contains(Object o)): O(n). В худшем случае необходимо пройти по всем элементам и сравнить их (используя метод equals).
• Итерация по всем элементам: O(n). Очень эффективна, особенно по сравнению с LinkedList.

Пример использования

import java.util.ArrayList;

public class ArrayListExample {
    public static void main(String[] args) {
        // Создание ArrayList для строк
        ArrayList<String> fruits = new ArrayList<>();

        // Добавление элементов
        fruits.add("Apple");
        fruits.add("Banana");
        fruits.add("Orange");
        System.out.println("После добавления: " + fruits); // [Apple, Banana, Orange]

        // Добавление по индексу
        fruits.add(1, "Mango"); // Сдвигает Banana и Orange вправо
        System.out.println("После вставки Mango: " + fruits); // [Apple, Mango, Banana, Orange]

        // Получение элемента по индексу
        String fruit = fruits.get(2);
        System.out.println("Элемент с индексом 2: " + fruit); // Banana

        // Удаление элемента по значению
        fruits.remove("Orange");
        System.out.println("После удаления 'Orange': " + fruits); // [Apple, Mango, Banana]

        // Удаление элемента по индексу
        fruits.remove(0);
        System.out.println("После удаления элемента с индексом 0: " + fruits); // [Mango, Banana]

        // Проверка наличия элемента
        boolean hasMango = fruits.contains("Mango");
        System.out.println("Содержит Mango? " + hasMango); // true

        // Размер списка
        System.out.println("Размер списка: " + fruits.size()); // 2

        // Итерация по списку
        System.out.println("Итерация с помощью for-each:");
        for (String f : fruits) {
            System.out.println(" - " + f);
        }
    }
}

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

Используйте ArrayList, когда:

• Вам нужен частый доступ к элементам по индексу (чтение).
• Основные операции — это добавление в конец списка и итерация.
• Размер коллекции часто меняется, но вставки/удаления в середину или начало происходят относительно редко.

Сравнение с LinkedList

В отличие от LinkedList (реализация на основе двусвязного списка), ArrayList:

• Быстрее для доступа по индексу (O(1) vs O(n)).
• Медленнее для вставки/удаления в середине списка (требуется сдвиг массива).
• Более эффективно использует память, так как хранит только данные, а не дополнительные ссылки (next/prev), как LinkedList.

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