Динамические массивы в 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.