Java ArrayList у зображеннях

Вітання! Сьогоднішня лекція 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(). Він "обрізає" довжину внутрішнього масиву до кількості елементів, що зберігаються в ньому на поточний момент. Тепер пам'яті виділяється стільки, скільки потрібно! :)