🔥 🚀 Важно для всех, кто работает с Java! 🔥
На JavaRocks ты найдешь уникальные туториалы, практические задачи и редкие книги, которых не найти в свободном доступе. Присоединяйся к нашему Telegram-каналу JavaRocks — стань частью профессионального сообщества!
Всем привет! Сегодня мы рассмотрим, что происходит при добавлении и удалении элементов в ArrayList, а также узнаем, как оптимизировать использование памяти.
Внутри ArrayList находится обычный массив, который фактически представляет собой хранилище данных. Его размер по умолчанию равен 10.
public static void main(String[] args) {
ArrayList<Car> cars = new ArrayList<>();
}Основные принципы при добавлении элементов в ArrayList
Посмотрим, как происходит добавление новых элементов.
В первую очередь необходимо проверить, достаточно ли места во внутреннем массиве и можно ли добавить еще один элемент. Если место есть, то новый элемент добавляется в конец списка.
“Конец списка” – это, конечно, не последняя ячейка всего массива (что было бы странно). Новый элемент записывается в первую свободную ячейку массива, следующую за последним элементом. Так, в нашем примере элемент добавляется по индексу cars.size().
Наглядный пример
Сейчас наш список пуст(cars.size() == 0), поэтому новый элемент будет добавлен в ячейку 0:
ArrayList<Car> cars = new ArrayList<>();
Car ferrari = new Car("Ferrari 360 Spider");
cars.add(ferrari);
Что происходит, если мы вставляем элемент в середину (между существующими элементами)?
public static void main(String[] args) {
ArrayList<Car> cars = new ArrayList<>();
Car ferrari = new Car("Ferrari 360 Spider");
Car bugatti = new Car("Bugatti Veyron");
Car lambo = new Car("Lamborghini Diablo");
Car ford = new Car("Ford Modneo");
cars.add(ferrari);
cars.add(bugatti);
cars.add(lambo);
cars.add(1, ford);// add ford to cell 1, which is already occupied
}Сначала проверяется, достаточно ли места в массиве. Если да, то элементы сдвигаются вправо, начиная с ячейки, в которую мы вставляем новый элемент.
Допустим, мы решили вставить элемент в ячейку 1. Тогда элемент из ячейки 3 копируется в ячейку 4, элемент 2 – в ячейку 3, элемент 1 – в ячейку 2.
В нашем примере:
– мы вставляем новый Car Object в ячейку с индексом 1, которая уже была занята другим элементом.
– все элементы, начиная с первого индекса, сдвигаются на одну ячейку вправо.
– промежуточный результат представлен на картинке:
Наш новый элемент вставляется в выбранную ячейку (1). Предыдущий элемент (bugatti) уже скопирован и смещен на одну ячейку вправо.
Посмотрим, что происходит, если в массиве недостаточно места для вставки новых элементов.
Конечно, после проверки выясняется, что места не хватает. В таком случае внутри ArrayList создается новый массив. Его размер можно рассчитать таким образом: размер старого массива умножаем на 1.5 и к этому прибавляем 1 (size*1.5 + 1). Так, в нашем примере размер нового массива будет равен 16. Все текущие элементы сразу же будут туда скопированы, а старый массив будет удален сборщиком мусора.
Итак, теперь есть место для нового элемента. Мы вставляем его в ячейку 3, которая уже занята другим элементом. Далее происходит все то, что мы уже рассмотрели выше: все элементы, начиная с третьего по индексу, смещаются на 1 вправо и т.д.
Удаление элементов в ArrayList
Поговорим об удалении элементов. При работе со стандартным массивом после удаления элементов образуются лакуны, и приходится каждый раз писать код для смещения элементов влево. В ArrayList этот механизм уже реализован на уровне класса. Достаточно только использовать метод remove()
Вот как наглядно происходит смещение элементов на ячейку влево:
Элемент lambo удален:
В данном случае мы удаляли элемент из середины. Закономерно, что удаление элемента из конца списка происходит быстрее, так как ресурсы для перемещения других элементов не затрачиваются.
Оптимизация использования памяти
Кроме того, важно отметить еще один момент. Представьте, что вам нужно создать ArrayList и вы заранее знаете, что в нем будет не менее 100 элементов. Если мы создадим ArrayList с размером по умолчанию, его придется расширять *6 раз, причем в каждом случае перемещая элементы. Согласитесь, это довольно ресурсозатратно.
*(10 –> 16 –> 25 –> 38 –> 58 –> 88 –> 133) по формуле size*1.5 + 1
Итак, лучше всего создать ArrayList определенного размера:
ArrayList<Car> cars = new ArrayList<>(100);Теперь память для массива из 100 элементов будет выделена сразу.
У такого подхода есть одно “но”: при удалении объектов из ArrayList размер внутреннего массива не уменьшается автоматически.
Предположим, у нас есть ArrayList с полностью заполненным внутренним массивом из 88 элементов:
В ходе работы программы мы удаляем 77 элементов, поэтому остается только 11:
В таком случае мы сталкиваемся с проблемой неэффективного использования памяти. Для оптимизации мы можем использовать специальный метод класса ArrayList: trimToSize()
Этот метод “обрезает” размер внутреннего массива до количества элементов, хранящихся в нем в данный момент.
Итак, проблема решена 🙂
Читайте также: «Java преобразование ArrayList в Array»
Перевод статьи «ArrayList in pictures».