С помощью какой структуры данных реализован ArrayList

ArrayList: структура данных и внутренняя реализация

ArrayList реализована с помощью динамического массива (resizable array). Это одна из наиболее важных и часто используемых структур данных в Java, и понимание её внутреннего устройства критично для написания эффективного кода.

Основная структура ArrayList

Внутри ArrayList использует обычный Java массив Object[] (или типизированный массив для параметризованных типов), который автоматически расширяется при необходимости:

public class ArrayList<E> extends AbstractList<E> 
        implements List<E>, RandomAccess, Cloneable, Serializable {
    
    /**
     * Внутренний массив для хранения элементов
     */
    transient Object[] elementData;
    
    /**
     * Текущее количество элементов
     */
    private int size;
    
    /**
     * Ёмкость (capacity) — размер внутреннего массива
     */
    private static final int DEFAULT_CAPACITY = 10;
}

Процесс добавления элемента (add operation)

Когда вы добавляете элемент в ArrayList, происходит следующее:

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) {
    // Вычисляем новую ёмкость (увеличиваем на 50%)
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // oldCapacity * 1.5
    
    if (newCapacity - minCapacity < 0) {
        newCapacity = minCapacity;
    }
    
    // Копируем старые данные в новый массив
    elementData = Arrays.copyOf(elementData, newCapacity);
}

Визуализация внутреннего состояния

Данные примеры показывают, как ArrayList растёт:

Шаг 1: Создание ArrayList
ArrayList<Integer> list = new ArrayList<>();

elementData: [null, null, null, null, null, null, null, null, null, null]
size: 0
capacity: 10

---

Шаг 2: Добавление 5 элементов
list.add(10);
list.add(20);
list.add(30);
list.add(40);
list.add(50);

elementData: [10, 20, 30, 40, 50, null, null, null, null, null]
size: 5
capacity: 10

---

Шаг 3: Добавление 11-го элемента (нужно расширение)
list.add(60);
list.add(70);
// ... добавим до 11-го

elementData: [10, 20, 30, 40, 50, 60, 70, null, null, null, null, null, null, null, null]
size: 11
capacity: 15 (было 10, увеличено на 50%)

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

Временная сложность основных операций:

public class ArrayListComplexity {
    
    /**
     * get(int index) — O(1)
     * Прямой доступ к элементу по индексу
     */
    public static <T> T get(ArrayList<T> list, int index) {
        // Просто возвращает элемент из массива
        return list.get(index); // O(1)
    }
    
    /**
     * add(E e) — O(1) amortized
     * Добавление в конец (обычно O(1), иногда O(n) при расширении)
     */
    public static <T> void addEnd(ArrayList<T> list, T element) {
        list.add(element); // O(1) amortized
    }
    
    /**
     * add(int index, E e) — O(n)
     * Вставка в середину требует сдвига всех элементов
     */
    public static <T> void addMiddle(ArrayList<T> list, int index, T element) {
        list.add(index, element); // O(n) — нужно сдвинуть элементы
    }
    
    /**
     * remove(int index) — O(n)
     * Удаление требует сдвига элементов влево
     */
    public static void removeAtIndex(ArrayList<Integer> list, int index) {
        list.remove(index); // O(n) — сдвиг элементов
    }
    
    /**
     * contains(Object o) — O(n)
     * Линейный поиск
     */
    public static <T> boolean contains(ArrayList<T> list, T element) {
        return list.contains(element); // O(n)
    }
}

Внутренняя реализация add(int index, E element)

Эта операция медленнее, потому что требует сдвига элементов:

public void add(int index, E element) {
    // Проверяем индекс
    if (index > size || index < 0) {
        throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }
    
    // Убеждаемся, что есть место
    ensureCapacityInternal(size + 1);
    
    // Сдвигаем элементы на один позицию вправо
    // Это O(n) операция!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    
    // Вставляем элемент
    elementData[index] = element;
    size++;
}

Сравнение с другими структурами данных

Практический пример использования

public class ArrayListExample {
    
    public static void main(String[] args) {
        // Создание ArrayList
        ArrayList<String> fruits = new ArrayList<>();
        
        // add() — эффективно, O(1)
        fruits.add("Apple");
        fruits.add("Banana");
        fruits.add("Cherry");
        System.out.println("Размер: " + fruits.size()); // 3
        System.out.println("Ёмкость: " + getCapacity(fruits)); // 10
        
        // get() — очень быстро, O(1)
        String first = fruits.get(0); // "Apple"
        
        // add(index, element) — медленно, O(n)
        fruits.add(1, "Blueberry"); // Вставляем в позицию 1
        // Результат: [Apple, Blueberry, Banana, Cherry]
        
        // remove() — медленно, O(n)
        fruits.remove(1); // Удаляем "Blueberry"
        
        // Итерация — O(n)
        for (String fruit : fruits) {
            System.out.println(fruit);
        }
    }
    
    // Получить текущую ёмкость (используем reflection)
    private static int getCapacity(ArrayList<?> list) {
        try {
            java.lang.reflect.Field field = ArrayList.class.getDeclaredField("elementData");
            field.setAccessible(true);
            Object[] array = (Object[]) field.get(list);
            return array.length;
        } catch (Exception e) {
            return -1;
        }
    }
}

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

ArrayList идеально подходит когда:

• Нужен частый доступ по индексу (get операция)
• Добавление происходит в основном в конец
• Нужна итерация по элементам
• Нужна случайная выборка элементов

Избегайте ArrayList когда:

• Часто добавляются/удаляются элементы в начало или середину (используйте LinkedList)
• Нужно сохранить порядок вставки при удалении (используйте LinkedHashSet)

Важные детали реализации

1. Амортизированная сложность добавления

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

2. Кратность расширения

Java использует коэффициент 1.5 (увеличение на 50%). Это хороший баланс между памятью и скоростью:

int newCapacity = oldCapacity + (oldCapacity >> 1); // oldCapacity * 1.5

3. Потокобезопасность

ArrayList НЕ является потокобезопасным. Для многопоточности используйте Collections.synchronizedList() или CopyOnWriteArrayList.

ArrayList — это фундаментальная структура данных в Java, и её понимание критично для написания эффективного кода.