ℹ️ Как устроен под капотом ArrayList?

ArrayList — это реализация динамического массива в Java. Он базируется на массиве, который может изменять свой размер по мере добавления элементов.

🔹 Массив как основа
В основе ArrayList лежит массив типа Object[]. Этот массив инициализируется с начальной емкостью (по умолчанию 10, если не указано иное).

🔹 Динамическое изменение размера
Когда добавляется элемент, а текущий массив заполнен, ArrayList расширяет массив, создавая новый с увеличенной емкостью — обычно это 1.5x от текущего размера. Старые данные копируются в новый массив с помощью System.arraycopy.

🔹 Добавление элементов
▪️ В среднем: добавление элемента занимает O(1), потому что в большинстве случаев просто добавляется новый элемент в конец массива, без необходимости его увеличения.
▪️ В худшем случае: добавление элемента может занять O(n), потому что, если внутренний массив переполняется, ArrayList вынужден создать новый массив большего размера и скопировать в него все существующие элементы.

🔹 Удаление элементов
При удалении элемента сдвигаются все последующие элементы на одну позицию влево, что приводит к сложностям:
▪️ Удаление по индексу: O(n) в худшем случае (сдвиг элементов после удаленного).
▪️ Удаление последнего элемента: O(1).

🔹Преимущества и недостатки

▪️ Преимущества: Быстрое добавление в конец, быстрый доступ по индексу O(1).
▪️ Недостатки: Медленное удаление или вставка в середине массива O(n), особенно при работе с большими коллекциями.