Робота з 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 — додавання нового числа, заради чого ми так старалися: