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

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

Устройство 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

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

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

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

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

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

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

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

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

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

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

Важно:

На этой картинке есть одна неточность.

Класс ArrayList не может хранить примитивные типы, поэтому вместо типа int он использует тип Integer. Контейнер хранит не значения 5-70, а ссылки на объекты типа Integer. Все пустые ячейки контейнера хранят null.


undefined
13
Задача
Java Syntax Pro, 13 уровень, 4 лекция
Недоступна
Создаем свой список
ArrayList — это список, который хранит динамически расширяемый массив элементов. Сейчас мы будем реализовывать свою версию списка, в котором хранятся строки. В классе CustomStringArrayList есть три поля: - String[] elements - это массив текущих элементов (в похожем массиве хранит значения ArrayList)

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

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

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

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

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

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

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

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

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

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

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

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

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