Небольшое введение. Все знают, что в массиве нельзя увеличить размер. Если мы изначально сказали, что там хранится 4 элемента, то добавить пятый никак не выйдет. Придётся создавать новый массив, а старый будет занимать место в памяти. Думаю, отчасти поэтому и придумали коллекции → такую структуру данных, где можно увеличивать размер. И один из самых популярных представителей коллекции → ArrayList.
ArrayList → это обычный список или, другими словами, динамический массив (массив, который может менять размер). И нам надо обязательно указать тип данных, который хранится в списке (String, Integer, Cat...). Заметьте, что тип может быть только ссылочным. Почему только ссылочные? Потому что лист использует дженерики. Примитивы добавить не выйдет, но, если очень хотите это сделать, то есть обёртки для каждого примитива.
Создаётся список так: ArrayList<String> list = new ArrayList<>(). Меня изначально интересовал вопрос, зачем пустые треугольные скобочки во второй половине. Дело в том, что раньше тип данных нужно было указывать с двух сторон. Времена изменились и теперь тип String достаточно написать один раз.
У листа есть два важных параметра:
- Capacity → ёмкость. По умолчанию, она равна 10. Именно столько элементов изначально может поместиться в список. Но ёмкость автоматически увеличивается, если пытаемся добавить 11-й элемент. Новая ёмкость вычисляется во формуле: предыдущая ёмкость * 1,5.
- Размер → то, сколько элементов сейчас находится в листе.
Что происходит при удалении и добавлении элемента в листе:
При добавлении элемента, если надо расширять ёмкость, то просто копируется старый массив и добавляется новый элемент. Это происходит автоматически. Старый просто лежит в памяти какое-то время. В принципе, мы могли бы аналогично использовать обычные массивы, но с листом просто не придётся писать всё самостоятельно.
Удаление: находится нужный элемент методом перебора и сравнения, он удаляется, все элементы после удаленного смещаются на 1 влево. Никаких дырок в листе нет. Но тут стоит заметить, что лист автоматически не сужается в отличии от увеличения. Что же делать, если изначально было 50 000 элементов, а потом осталось всего 2? Для этого существуется отличный метод trimToSize(). Он обрежет массив по количеству элементов. Зачем обрезать? Чтобы у нас массив не занимал памяти для 50 000 элементов, когда нужно только 2.
Что за параметр ensure и зачем он нужен?
Представьте, что есть лист с 10 элементами. Нужно добавить ещё 50 000. Если мы просто добавим, то сколько раз лист будет увеличиваться? Изначально ёмкость равна 10, потом увеличится в полтора раза, потом ещё раз в полтора раза и так много раз. Старые массивы останутся в памяти мусором. Конечно, их потом удалят, но ведь не моментально. Какое-то время они просто будут занимать ценное место. ensure проверяет, есть ли место для 50 000 элементом и, если нет, то сразу увеличивает. Т.е. это происходит всего один раз, а не много раз с умножением на 1,5.
Сложности в листе.
Получение элемента → О(1). Просто потому что это массив и зная индекс мы легко найдём значение.
Мы можем очень быстро вставить элемент в конец. Просто потому что это легко. Находим последний элемент и вставляем. Сложность → О(1).
А вот вставить на первое место будет сложнее всего. Почему? Потому что нам надо каждый последующий элемент сместить вправо. Сложность тут будет O(n).
Удаление по значению. Тут последовательно сравнивается каждый элемент. Сложность: O(n).
Удаление по индексу: в зависимости от того, где находится наш элемент. Найти его легко, но ведь потом будет смещение.
