Java ArrayList в картинках

Привіт! Сьогоднішня лекція про ArrayList буде з одного боку простішою, а з іншого — складнішою, ніж попередні. Складнішою, тому що сьогодні ми зазирнемо “під капот” ArrayList’а і будемо вивчати, що ж з ним відбувається під час операцій. З іншого боку, у цій лекції майже не буде коду — в основному картинки та пояснення. Отже, поїхали :) Як ти вже знаєш, всередині ArrayList’а знаходиться звичайний масив, який і є сховищем даних. У більшості випадків ми не вказуємо точний розмір списку. Але ж внутрішній масив повинен мати якийсь розмір! Так і є. Його розмір за замовчуванням — [10].

public static void main(String[] args) {
   ArrayList<Car> cars = new ArrayList<>();
}

Для початку подивимося, як виглядає додавання нового елемента. У першу чергу здійснюється перевірка — чи достатньо місця у внутрішньому масиві і чи поміститься ще один елемент. Якщо місце є, новий елемент додається в кінець списку. Коли ми говоримо “в кінець” — мається на увазі не остання комірка масиву (це було б дивно). Мається на увазі комірка, наступна за останнім поточним елементом. Її індекс буде дорівнювати cars.size(). Наш список зараз порожній (cars.size() = 0). Відповідно, новий елемент буде додано в комірку з індексом 0.

ArrayList<Car> cars = new ArrayList<>();
Car ferrari = new Car("Ferrari 360 Spider");
cars.add(ferrari);

Тут все зрозуміло. Що буде, якщо вставка буде здійснюватися в середину, тобто між кількома елементами?

public static void main(String[] args) {
   ArrayList<Car> cars = new ArrayList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");
   Car ford = new Car("Ford Modneo");
  
   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
  
   cars.add(1, ford);//додаємо ford у комірку 1, яка вже зайнята
}

Знову ж таки, спочатку перевіряється, чи достатньо місця у масиві. Якщо місця достатньо, відбувається зсув елементів праворуч, починаючи з тієї комірки, куди ми вставляємо новий елемент. Ми вставляємо у комірку з індексом 1. Тобто елемент із комірки 3 копіюється у комірку 4, елемент 2 — у комірку 3, елемент 1 — у комірку 2. Після цього наш новий елемент вставляється на своє місце. Попередній елемент (bugatti) вже був скопійований звідти на нове місце. Тепер давай розберемося, як би відбувався цей процес, якби місця для вставки у масиві не було. Спочатку, звичайно, здійснюється перевірка — чи достатньо місця. Якщо виявляється, що місця не вистачає, всередині ArrayList’а створюється новий масив розміром (розмірСтарогоМасиву * 1.5) + 1 У нашому випадку новий масив буде мати розмір 16 комірок. Туди одразу ж будуть скопійовані всі поточні елементи. Старий масив буде видалений збирачем сміття, і залишиться тільки новий, розширений. Тепер вільне місце для нового елемента є. Ми вставляємо його в комірку 3, яка зайнята. Тепер починається вже знайома тобі процедура. Усі елементи, починаючи з індексу 3, зсуваються на одну комірку праворуч, і новий елемент спокійно додається. І тепер вставка пройшла успішно! Зі вставкою розібралися. Тепер поговоримо про видалення елементів. Як ти пам’ятаєш, при роботі з масивами ми стикнулися з проблемою: при видаленні залишалися “дірки”. Єдиним виходом було зсовувати елементи вліво щоразу при видаленні, причому писати код для зсуву доводилося самостійно. ArrayList працює за тим самим принципом, але в ньому цей механізм уже реалізовано автоматично. Ось як це виглядає: І в підсумку ми отримуємо потрібний результат: Елемент lambo був успішно видалений. Тут ми робили видалення з середини. Зрозуміло, що видалення з кінця списку буде швидшим, оскільки потрібний елемент забирається без зсуву всіх інших. Давай ще раз пройдемося по розмірах внутрішнього масиву та його зберіганню в пам’яті. Розширення масиву — процес, що займає певну кількість ресурсів. Тому не варто створювати ArrayList з розміром за замовчуванням, якщо ти точно знаєш, що в ньому буде не менше 100 елементів. Поки ти дійдеш до вставки 100-го елемента, внутрішній масив розшириться 6 разів, щоразу з перенесенням усіх елементів.

• з 10 елементів до 16
• з 16 елементів до 25
• з 25 до 38
• з 38 до 58
• з 58 до 88
• з 88 до 133 (за формулою (розмірСтарогоМасиву * 1.5)+1)

Звісно, це у плані ресурсів доволі затратно. Тому, якщо ти знаєш якусь (хоч приблизну) кількість елементів, краще одразу створити список з масивом визначеного розміру:

ArrayList<Car> cars = new ArrayList<>(100);

Тепер у пам’яті буде одразу виділений масив на 100 елементів, більш ефективний, бо не будуть витрачатися ресурси на розширення. Є й зворотний бік медалі. При видаленні об’єктів з ArrayList розмір внутрішнього масиву не зменшується автоматично. Наприклад, у нас є ArrayList із внутрішнім масивом на 88 елементів, який повністю заповнений: У процесі роботи програми ми видаляємо з нього 77 елементів, і в ньому залишається всього 11: Уже здогадався, в чому проблема? Звісно, в неефективному використанні пам’яті! Ми використовуємо всього 11 комірок, при цьому у нас виділена пам’ять на 88 елементів — це в 8 разів більше, ніж потрібно! Для проведення оптимізації в цьому випадку можна використовувати спеціальний метод класу ArrayList — trimToSize(). Він “обрізає” довжину внутрішнього масиву до кількості елементів, які в ньому зберігаються на поточний момент. Тепер пам’ять виділяється стільки, скільки потрібно! :)