Динамічні масиви в Java

Під час створення програм різного ступеня складності кожен розробник використовує безліч типів даних, зокрема і масиви. Ця структура добре підходить для зберігання набору одного типу, дає класну продуктивність, та й загалом зручна. Істотний мінус масивів - статичність: необхідно заздалегідь ставити їх розмір. Однак програмісти поки що не вміють передбачати майбутнє (якщо, звичайно, не з'явиться ІІ, який оброблятиме інформацію неймовірно швидко і зможе передбачати якісь події). Тому створабо структуру, яка зможе змінювати розмір в момент роботи програми. Вона отримала назву динамічний масив .

Динамічні масиви в курсі JavaRush

Дуже зрозуміло ця тема розкривається на 7 і частково - на 8 рівні курсу JavaRush в квесті Java Syntax. Протягом кількох лекцій та цілих 18 завдань розкриваються ключові питання, види динамічних масивів та різниця між ними, включаючи продуктивність. Ця тема є максимально важливою, оскільки динамічні масиви позбавляють розробника від депресії, головного болю та економлять неймовірну кількість часу.

Що таке динамічний масив?

Динамічний масив – це масив, який вміє змінювати свій розмір під час виконання програми. У Java цю роль грають переважно класи ArrayList і LinkedList. На відміну від масивів, ArrayList і LinkedList містять тільки типи посилань даних, тобто зберегти в них можна тільки об'єкти. На щастя, в Java існують механізми автоупаковки та автозапаковування, які дозволяють зберігати в динамічних масивах примітивні типи. Подібно до статичного масиву, динамічний однорідний, тобто може зберігати один-єдиний тип даних. Однак завдяки механізму успадкування і грамотному використанню інтерфейсів можна зберігати в одному динамічному масиві цілий спектр різноманітних класів, які успадковані від одного загального, але про це нижче. Тобто статичний масив працює так: Адинамічний масив Java спрацює наступним чином (продовжуємо схему з третього кроку): Java використовується спеціальна нативна функція для копіювання масиву, тому такий "переїзд" обходиться не дуже дорого.

Навіщо потрібний динамічний масив?

Динамічний масив Java використовується для обробки наборів однорідних даних, розмір яких невідомий на момент написання програми. Наприклад, потрібно зберегти в кеші дані кожного клієнта, який на даний момент використовує програму. Неможливо передбачити кількість таких клієнтів наперед. Без динамічних масивів цю проблему можна вирішити такими варіантами:

1. Створити масив великого розміру, який з ймовірністю 100% покриє потребу;
2. Створити статичний масив, який виконуватиме функцію буфера;
3. Застосувати інші динамічні структури, наприклад, множини.

Перший варіант підійде лише у разі жорстко обмеженого діапазону. В інших випадках такий масив займе велике місце в пам'яті, що є максимально неефективним. Другий вимагатиме реалізації додаткових механік очищення буфера, зчитування тощо. У третього також є недоліки через різницю у функціональності.

Що виконує роботу динамічного масиву в Java

У мові Java як динамічний масив виступають класи ArrayList і LinkedList. Найчастіше використовується ArrayList, оскільки він виконує роль класичного масиву, на відміну LinkedList, який реалізує концепцію двозв'язаного списку. Про нього йтиметься трохи пізніше.

ArrayList, LinkedList — поняття та правила роботи

ArrayList це класичний масив, який може розширюватися в момент виконання програми. У його основі лежить звичайний масив: його розмір під час створення — 10 елементів. Збільшення розміру ємність збільшується. Правила, за якими працює ArrayList:

• Також, як і статичний масив, індексується з 0;
• Вставка в кінець та доступ за індексом дуже швидкі - О(1);
• Щоб вставити елемент на початок або середину, потрібно скопіювати всі елементи на одну комірку вправо, а потім вставити новий елемент на необхідну позицію;
• Доступ за значенням залежить кількості елементів — О(n);
• На відміну від класичного масиву може зберігати null;

У випадку з LinkedList дещо складніше: в його основі лежить двозв'язаний список. Тобто структурно цей динамічний масив Java являє собою кілька розкиданих об'єктів, які посилаються один на одного. Легше пояснити малюнки. Усередині LinkedList ми маємо головний об'єкт — Head, який зберігає інформацію про кількість елементів, а також посилання на перший і останній елементи: Зараз поле size = 0, а firstі last = null. Кожен елемент, який додається до цього списку, містить окремий внутрішній об'єкт. Давай додамо елемент Johnny: Тепер у нас з'явилася нода зі значенням Johnny. У головного елемента посилання перший і останній елемент вказують на нову ноду. Цей об'єкт також має посилання на попередній і наступний елементи. Посилання на попередній у нього завжди буде null, тому що це перший елемент, а посилання на наступний - null, тому що його поки що немає. Давайте це виправимо: Доданий новий елемент, зі значенням “Watson”, який став другим. Слід звернути увагу, що перший елемент поле nextвказує на наступний елемент, а в нового поле previousвказує на попередній. Головний елемент посилання на останній елемент вказує тепер на нову ноду. На наступній схемі показаний принцип додавання елементів до середини списку: Додано новий елемент “Hamish”. Щоб вставити його в середину списку, достатньо переналаштувати посилання на елементи, як показано на малюнку. Дані ілюстрації пояснюють процес роботи двозв'язкового списку на верхньому рівні, не вдаючись до подробиць. Підсумовуючи розповідь про LinkedList, можна вивести кілька правил його роботи:

• Також, як і масив, індексується з 0;
• Доступ до першого та останнього елемента не залежить від кількості елементів — О(1);
• Отримання елемента за індексом, вставка чи видалення із середини списку залежить від кількості елементів — О(n);
• Можна використовувати механізм ітератора: тоді вставка та видалення відбуватимуться за константний час;
• На відміну від класичного масиву може зберігати null.

Приклади коду

Пройдемося трохи за прикладами. Фрагменти коду включають приклади як для ArrayList, так і для LinkedList.

створення

// Создаем новый список
ArrayList<String> arrayList = new ArrayList<>();
// Создается новый список и указывается начальный размер внутреннего массива
ArrayList<String> arrayListLarge = new ArrayList<>(100000);

// Создаем новый LinkedList
LinkedList<String> linkedList = new LinkedList<>();

Додавання елемента

// Новый элемент добавляется в конец
arrayList.add("Johhny");
// Новый элемент добавляется в указанную позицию (в данном случае — в начало)
arrayList.add(0, "Watson");

// Новый элемент добавляется в конец двусвязного списка
linkedList.add("Java");
// Новый элемент добавляется в нулевую позицию списка:
linkedList.addFirst("I think");
// Новый элемент добавляется в конец списка
linkedList.addLast("language");
// Новый элемент добавляется в указанную позицию
linkedList.add(2, "is a terrific");

// Получение размера списков
int arraySize = arrayList.size(); // 2
int linkedSize = linkedList.size(); // 4

На перший погляд методи add()І addLast()виконують один і той же функціонал, проте метод add()прийшов у LinkedList з інтерфейсу List, а метод addLast– з інтерфейсу Deque. LinkedList реалізує обидва ці інтерфейси. Хорошою практикою в даному випадку буде використовувати той метод, який найбільше підходить за контекстом. Якщо LinkedList використовується як черга, то найкраще використовувати метод addLast. Якщо LinkedList використовується як список, доречно використовуватиме add().

Видалення елемента

// Удаление елемента по индексу
arrayList.remove(0);
// Удаление елемента по значению
arrayList.remove("Johnny");

// Удаление первого елемента в списке
linkedList.removeFirst();
// Удаление первого елемента в списке, фактически вызов предыдущего метода
linkedList.remove();
// Удаление последнего елемента в списке
linkedList.removeLast();
// Удаление первого вхождения елемента в список
linkedList.removeFirstOccurrence("language");
// Удаление последнего вхождения елемента в список
linkedList.removeLastOccurrence("Java");
// Удаление по индексу
linkedList.remove(2);

Якщо видаляється об'єкт за індексом, метод повертає віддалений об'єкт. Якщо об'єкт видаляється за значенням (або LinkedList видаляється перший або останній елементи), метод повертає true , якщо об'єкт знайдений і видалений, false - в іншому випадку.

Доступ до елемента та пошук у списку

// Доступ к элементу по индексу
String arrayElement = arrayList.get(2);
// Поиск елемента по значению
int arrayIndex = arrayList.indexOf("Watson");
// Поиск последнего индекса вхождения елемента в список
int lastArrayIndex = arrayList.lastIndexOf("Watson");

// Доступ по индексу
String linkedElement = linkedList.get(3);
// Получение первого елемента
String firstLinkedElement = linkedList.getFirst();
// Получение последнего елемента
String lastLinkedElement = linkedList.getLast();

// Поиск елемента по значению
int linkedIndex = linkedList.indexOf("Java");
// Поиск последнего индекса вхождения елемента в список
int lastLinkedIndex = linkedList.lastIndexOf("Java");

Обхід у циклі

// Использование обычного цикла
for(int i = 0; i<arrayList.size(); i++) {
  String value = arrayList.get(i);
  System.out.println(value);
}

for(int i = 0; i<linkedList.size(); i++) {
  String value = linkedList.get(i);
  System.out.println(value);
}

// Использование цикла for-each
for(String s : arrayList) {
  System.out.println(s);
}

for(String s : linkedList) {
  System.out.println(s);
}

Тут варто сказати кілька слів про пошук. Багато розробників-початківців при пошуку елемента в списку починають пошук у циклі, порівнюючи всі елементи з шуканим, незважаючи на наявність методів indexOf()і lastIndexOf(). Також можна використовувати метод contains()для отримання факту наявності елемента у списку:

boolean isContainsSherlock = arrayList.contains("Sherlock");
boolean isContainsPhp = linkedList.contains("Php");

Посилання на додаткове читання

1. Ось тут є чудова стаття про видалення елементів з ArrayList. За рахунок того, що це динамічний масив Java , є багато тонкощів у видаленні елементів.
2. Тут детально ілюстровано роботу ArrayList.
3. Трохи докладніше про LinkedList.
4. Пара статей з хабра про ArrayList і LinkedList .