1. Как устроен ArrayList
ArrayList
— самый распространённый класс в Java для хранения элементов. Так как же устроен этот ArrayList
и почему он так всем нравится?
Устройство ArrayList
простое и гениальное по своей сути. Внутри каждого объекта ArrayList
есть два поля:
- Массив со списком элементов
- Переменная
size
, которая хранит количество элементов списка
Внутри объекта ArrayList
содержится самый обычный массив! Но не только. Там есть еще переменная size, которая хранит длину списка. Вот как это работает:
Изначально длина массива внутри списка — 10 элементов. А переменная size
равна 0.
Если в список добавить элемент, он будет сохранен в 0-ю ячейку массива, а size
увеличится до 1.
Если добавить еще один элемент, он будет сохранен в 1-ю ячейку, а size
снова увеличится на 1 и теперь будет равняться двум.
Если при добавлении очередного элемента в список в массиве уже нет места, в методе add()
происходит следующее:
- создается новый массив в полтора раза длиннее предыдущего
- в него копируются все элементы из существующего массива
- в объекте
ArrayList
вместо старого массива сохраняется ссылка на новый. - В 10-ю ячейку нового массива записывается переданный элемент
- 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 — новое количество элементов в списке. К размеру массива оно не имеет никакого отношения.
На этой картинке есть одна неточность.
Класс ArrayList
не может хранить примитивные типы, поэтому вместо типа int
он использует тип Integer
. Контейнер хранит не значения 5-70, а ссылки на объекты типа Integer
. Все пустые ячейки контейнера хранят null
.
3. Увеличение длины списка
Давайте разберем, что происходит внутри списка, когда в его массиве заканчиваются свободные ячейки.
Допустим, у нас был список из 10 элементов:
Мы решили добавить в него число 100, вот что при этом произойдет в методе add()
:
Шаг 1 — создание нового массива:
Шаг 2 — копирование всех элементов из старого массива в новый:
Шаг 3 — замена массива (изменение ссылки на массив внутри объекта ArrayList
):
Шаг 4 — добавление нового числа, ради чего мы так старались:
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ