Вітання! Сьогоднішня лекція
Складніше, тому що сьогодні ми заглянемо під капот
Спочатку подивимося, як виглядає додавання нового елемента. Насамперед проводиться перевірка — чи достатньо у внутрішньому масиві місця та чи влізе ще один елемент. Якщо місце є, новий елемент додається до кінця списку. Коли ми говоримо "в кінець" - мається на увазі не останній осередок масиву (це було б дивно). Мається на увазі осередок, що йде за останнім поточним елементом. Її індекс дорівнюватиме
Тут усе зрозуміло. Що буде, якщо вставка буде здійснюватися в середину, тобто між кількома елементами?
наш новий елемент вставляється на своє місце. Попередній елемент (
Тепер давай розберемося, як відбувався цей процес, якби місця для вставки в масиві не було.
Спочатку, звичайно, здійснюється перевірка, чи достатньо місця. Якщо з'ясовується, що місця не вистачає, усередині
Старий масив буде видалено збирачем сміття, і залишиться лише новий, розширений. Тепер є вільне місце для нового елемента. Ми вставляємо його в комірку 3, яка зайнята. Тепер починається вже знайома тобі процедура. Всі елементи, починаючи з індексу 3, зсуваються на одну комірку праворуч, і новий елемент спокійно додається.
І тепер вставка пройшла вдало! Зі вставкою розібралися. Тепер поговоримо про видалення елементів . Як ти пам'ятаєш, при роботі з масивами ми зіткнулися з проблемою: при видаленні в ньому залишалися дірки. Єдиним виходом було зрушувати елементи влівощоразу при видаленні, причому писати код для зсуву доводилося самостійно.
Ось як це виглядає:
І в результаті ми отримуємо потрібний результат:
Елемент
У процесі роботи програми ми видаляємо з нього 77 елементів, і в ньому залишається всього 11:
Вже здогадався, в чому проблема? Звісно, у неефективному використанні пам'яті! Ми використовуємо всього 11 осередків, при цьому у нас виділено пам'ять на 88 елементів – це у 8 разів більше, ніж потрібно! Для проведення оптимізації в даному випадку можна використовувати спеціальний метод
Тепер пам'яті виділяється стільки, скільки потрібно! :)
ArrayList
буде з одного боку простішою, а з іншого — складнішою, ніж попередні. ![Робота ArrayList в картинках - 1](https://cdn.javarush.com/images/article/e5b7b68d-eaa2-4335-aae5-b0b8994b8f75/800.jpeg)
ArrayList
'a і вивчатимемо, що ж з ним відбувається під час операцій. З іншого боку, у цій лекції майже не буде коду — переважно картинки та пояснення. Отже, поїхали :) Як ти вже знаєш, всередині ArrayList
знаходиться звичайний масив, який і виступає сховищем даних. Найчастіше ми не вказуємо точний розмір списку. Але ж внутрішній масив повинен мати якийсь розмір! Так і є. Його розмір за умовчанням - [10] .
public static void main(String[] args) {
ArrayList<Car> cars = new ArrayList<>();
}
![Робота ArrayList в картинках - 2](https://cdn.javarush.com/images/article/4fd1f54f-2017-42da-ac64-ce6810bffe44/800.jpeg)
cars.size()
. Наш список зараз порожній ( cars.size() = 0
). Відповідно, новий елемент буде доданий у комірку з індексом 0
.
ArrayList<Car> cars = new ArrayList<>();
Car ferrari = new Car("Ferrari 360 Spider");
cars.add(ferrari);
![Робота ArrayList в картинках - 3](https://cdn.javarush.com/images/article/d5072edc-9aa4-4cf0-b865-31bcaa77d873/800.jpeg)
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. Після цього ![Робота ArrayList в картинках - 4](https://cdn.javarush.com/images/article/c5087e13-195d-4e92-876c-79ce39e1b854/800.jpeg)
bugatti
) вже скопіювався звідти на нове місце. ![Робота ArrayList в картинках - 5](https://cdn.javarush.com/images/article/bafcc808-886b-40c2-979e-d711e0f85628/800.jpeg)
![Робота ArrayList в картинках - 6](https://cdn.javarush.com/images/article/e2d01f2e-5399-459b-b397-1a2ae3cab42a/800.jpeg)
ArrayList
'a створюється новий масив розміром (розмір Старого Масиву * 1.5) + 1 У нашому випадку новий масив матиме розмір 16 осередків. Туди відразу будуть скопійовані всі поточні елементи. ![Робота ArrayList в картинках - 7](https://cdn.javarush.com/images/article/57fe0027-630c-422b-9bb7-01007c46ab3a/800.jpeg)
![Робота ArrayList в картинках - 8](https://cdn.javarush.com/images/article/6e1b2e29-68c1-4a1c-b768-3efe82d05bce/800.jpeg)
ArrayList
працює за тим самим принципом, але в ньому цей механізм уже реалізовано автоматично. ![Робота ArrayList в картинках - 9](https://cdn.javarush.com/images/article/49ca56a1-5b88-4e66-ae1e-a713cf24bb18/800.jpeg)
![Робота ArrayList в картинках - 10](https://cdn.javarush.com/images/article/f27da1f8-e1ba-4848-8261-9014f23e74be/800.jpeg)
![Робота ArrayList в картинках - 11](https://cdn.javarush.com/images/article/804aa243-0faf-44af-a5d1-3153b4b874f8/800.jpeg)
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 елементів, який повністю заповнений: ![Робота ArrayList в картинках - 13](https://cdn.javarush.com/images/article/d8379a63-8e10-4f25-8612-01d56bc08a7b/800.jpeg)
![Робота ArrayList в картинках - 14](https://cdn.javarush.com/images/article/7e91b172-90f9-48b4-92a5-662609eb8f06/800.jpeg)
ArrayList
класуtrimToSize()
. Він "обрізає" довжину внутрішнього масиву до кількості елементів, що зберігаються в ньому на поточний момент. ![Робота ArrayList в картинках - 15](https://cdn.javarush.com/images/article/fafe80bc-38bf-4df1-bba9-e34c446f0bb3/800.jpeg)
ПЕРЕЙДІТЬ В ПОВНУ ВЕРСІЮ