Работа с ArrayList

1. Как устроен ArrayList

ArrayList — самый распространённый класс в Java для хранения элементов. Так как же устроен этот ArrayList и почему он так всем нравится?

Устройство ArrayList простое и гениальное по своей сути. Внутри каждого объекта ArrayList есть два поля:

• Массив со списком элементов
• Переменная size, которая хранит количество элементов списка

Внутри объекта ArrayList содержится самый обычный массив! Но не только. Там есть еще переменная size, которая хранит длину списка. Вот как это работает:

Изначально длина массива внутри списка — 10 элементов. А переменная size равна 0.

Если в список добавить элемент, он будет сохранен в 0-ю ячейку массива, а size увеличится до 1.

Если добавить еще один элемент, он будет сохранен в 1-ю ячейку, а size снова увеличится на 1 и теперь будет равняться двум.

Если при добавлении очередного элемента в список в массиве уже нет места, в методе add() происходит следующее:

1. создается новый массив в полтора раза длиннее предыдущего
2. в него копируются все элементы из существующего массива
3. в объекте ArrayList вместо старого массива сохраняется ссылка на новый.
4. В 10-ю ячейку нового массива записывается переданный элемент
5. size увеличивается на 1 и теперь будет равняться 11

Аналогично при добавлении (вставке) элемента в середину списка. Существующие элементы сдвигаются на 1 вправо, и в свободную ячейку массива записывается нужный элемент.

Самые основные сценарии использования списка мы сейчас рассмотрим:

2. Добавление элемента в ArrayList

Давайте разберём, что происходит внутри списка, когда в него добавляются элементы. Сразу после создания объекта ArrayList мы имеем в памяти примерно такую картину:

У нас есть объект типа ArrayList, внутри которого два поля (две переменные): массив (data) и количество элементов (size). data хранит ссылку на контейнер (массив) из 10 элементов.

Если мы решим добавить в массив число 5, получится такая картина:

В массиве теперь хранится элемент 5, а переменная size == 1.

Если сейчас кто-то вызовет метод size() у нашего объекта ArrayList, он получит количество элементов списка — 1. Количество элементов списка — это не размер массива.

Ни действительный размер массива, ни сам массив никогда не будут доступны (видны) вне объекта ArrayList. Это внутренние данные ArrayList, и они всегда ими останутся.

Давайте добавим в список еще 7 чисел: 10, 20, 30, 40, 50, 60, 70.

Тогда картина в памяти будет уже такой:

Если сейчас вызвать метод size(), он вернет число 8 — новое количество элементов в списке. К размеру массива оно не имеет никакого отношения.

3. Увеличение длины списка

Давайте разберем, что происходит внутри списка, когда в его массиве заканчиваются свободные ячейки.

Допустим, у нас был список из 10 элементов:

Мы решили добавить в него число 100, вот что при этом произойдет в методе add() :

Шаг 1 — создание нового массива:

Шаг 2 — копирование всех элементов из старого массива в новый:

Шаг 3 — замена массива (изменение ссылки на массив внутри объекта ArrayList):

Шаг 4 — добавление нового числа, ради чего мы так старались: