Вітання! Сьогоднішня лекція
ArrayList
буде з одного боку простішою, а з іншого — складнішою, ніж попередні. Складніше, тому що сьогодні ми заглянемо під капот ArrayList
'a і вивчатимемо, що ж з ним відбувається під час операцій. З іншого боку, у цій лекції майже не буде коду — переважно картинки та пояснення. Отже, поїхали :) Як ти вже знаєш, всередині 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
'a створюється новий масив розміром (розмір Старого Масиву * 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()
. Він "обрізає" довжину внутрішнього масиву до кількості елементів, що зберігаються в ньому на поточний момент. Тепер пам'яті виділяється стільки, скільки потрібно! :)
ПЕРЕЙДІТЬ В ПОВНУ ВЕРСІЮ