20. Как устроен ArrayList, сложность основных операций.

ArrayList хранит элементы в динамическом массиве. Элементы ArrayList могут быть абсолютно любых типов в том числе и null.

Основное преимущество такой коллекции над массивом – это расширяемость – увеличение длины при надобности.

Если в этом массиве заканчивается место, то создаётся второй массив побольше, куда копируются все элементы из первого. Затем второй массив занимает место первого, а первый – выбрасывается (будет уничтожен сборщиком мусора).

Длина нового массива рассчитывается так (3*n)/2+1, где n – это длина старого массива. Т.е. если старый массив был длиной 100 элементов, то новый будет 300/2+1 = 151

При добавлении элемента в середину ArrayList, все элементы справа от него копируются на 1 позицию вправо, а затем в пустую ячейку добавляется новый элемент.

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

При удалении элемента из середины, все элементы справа от него копируются на 1 позицию влево. Сам массив не укорачивается (можно укоротить через trimToSize()).

Особенности

• Быстрый доступ к элементам по индексу за время O(1);
• Доступ к элементам по значению за линейное время O(n);
• Медленный, когда вставляются и удаляются элементы из «середины» списка;
• Позволяет хранить любые значения в том числе и null;
• Не синхронизирован.

Предыдущий вопрос: 19. Расскажите про интерфейс List

Следующий вопрос: 21. Как устроен LinkedList, сложность основных операций.

Все вопросы по теме: список

Все темы: список

Вопросы/замечания/предложения/нашли ошибку:напишите мне