1. Як влаштовано ArrayList
ArrayList — найпоширеніший клас у Java для зберігання елементів. Як же влаштовано цей ArayList і чому він так усім подобається?
Будова ArrayList проста й геніальна за своєю сутністю. Усередині кожного об'єкта ArrayList є два поля:
- Масив зі списком елементів
- Змінна
size, яка зберігає кількість елементів списку
Усередині об'єкта ArrayList міститься звичайнісінький масив! Але не тільки. Там є ще змінна size, яка зберігає довжину списку. От як це працює.
Початкова довжина масиву всередині списку — 10 елементів. А змінна size дорівнює 0.
Якщо в список додати елемент, його буде збережено в 0-ву комірку масиву, а size збільшиться до 1.
Якщо додати ще один елемент, його буде збережено в 1-шу комірку, а size знову збільшиться на 1 і тепер дорівнюватиме двом.
Якщо при спробі додавання чергового елемента до списку в масиві вже немає місця, у методі add() відбувається от що:
- Створюється новий масив, у півтора раза довший за попередній.
- У нього копіюються всі елементи з наявного масиву.
- В об'єкті
ArrayListзамість старого масиву зберігається посилання на новий. - В 11-ту комірку нового масиву записується переданий елемент.
- 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 — додавання нового числа, заради чого ми так старалися:
ПЕРЕЙДІТЬ В ПОВНУ ВЕРСІЮ