Динамические массивы в Java

Динамический массив это массив, который умеет менять свой размер во время работы программы; в Java его роль играет ArrayList (внутри обычный массив, который при заполнении копируется в новый, в полтора раза больший), а рядом с ним часто ставят LinkedList, хотя внутри у него не массив, а двусвязный список. При создании программ разной степени сложности каждый разработчик использует множество типов данных, в том числе и массивы. Эта структура хорошо подходит для хранения набора одного типа, дает классную производительность, да и в целом удобна. Существенный минус массивов это статичность: необходимо заранее задавать их размер. Однако программисты пока не умеют предсказывать будущее (если, конечно, не появится ИИ, который будет обрабатывать информацию невероятно быстро и сможет предугадывать какие-либо события). По этой причине создали структуру, которая сможет изменять размер в момент работы программы. Она получила название динамический массив.

Кратко

• Обычный массив создается с фиксированной длиной, и одиннадцатый элемент в массив на десять ячеек не положить; динамический массив при заполнении сам создает массив побольше и переносит в него данные.
• ArrayList это и есть динамический массив: начальная емкость 10, при нехватке места массив копируется в новый примерно в полтора раза больший, копирование делает нативный System.arraycopy.
• LinkedList устроен иначе: это двусвязный список из узлов со ссылками previous и next, а сам список хранит size, first и last.
• У ArrayList доступ по индексу и добавление в конец за O(1), вставка в начало или середину за O(n) из-за сдвига элементов; у LinkedList наоборот: концы за O(1), доступ по индексу за O(n).
• Оба хранят только объекты (примитивы через автоупаковку) и допускают null; размер узнают через size(), а не length.
• По умолчанию берите ArrayList; LinkedList оправдан, когда список используют как очередь или много вставляют и удаляют через итератор.

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

Очень доходчиво и понятно эта тема раскрывается на 7 и частично на 8 уровне курса JavaRush в квесте Java Syntax. В течение нескольких лекций и целых 18 задач раскрываются ключевые вопросы, виды динамических массивов и разница между ними, включая производительность. Эта тема максимально важная, так как динамические массивы избавляют разработчика от депрессии, головной боли и экономят невероятное количество времени.

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

Динамический массив это массив, который умеет изменять свой размер во время выполнения программы. В Java эту роль играют в основном классы ArrayList и LinkedList. В отличие от массивов, ArrayList и LinkedList содержат только ссылочные типы данных, то есть сохранить в них можно только объекты. К счастью, в Java существуют механизмы автоупаковки и автораспаковки, которые позволяют хранить в динамических массивах примитивные типы. Подобно статическому массиву, динамический однороден, то есть может хранить один-единственный тип данных. Однако, благодаря механизму наследования и грамотному использованию интерфейсов, можно сохранять в одном динамическом массиве целый спектр разнообразных классов, которые унаследованы от одного общего: в List<Animal> поместятся и Cat, и Dog. То есть статический массив работает так: А динамический массив в Java сработает следующим образом (продолжаем схему с третьего шага): В Java используется специальная нативная функция для копирования массива (System.arraycopy), поэтому такой “переезд” обходится не очень дорого.

Зачем нужен динамический массив?

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

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

Первый вариант подойдет только в случае жестко ограниченного диапазона. В остальных случаях такой массив займет большое место в памяти, что максимально неэффективно. Второй потребует реализации дополнительных механик очистки буфера, считывания и так далее. У третьего также есть недостатки из-за различия в функциональности.

Что выполняет работу динамического массива в Java

В языке Java в качестве динамического массива выступают классы ArrayList и LinkedList. Чаще всего используется ArrayList, так как он выполняет роль классического массива, в отличие от LinkedList, который реализует концепцию двусвязного списка. О нем речь пойдет немного позже.

ArrayList и LinkedList: понятия и правила работы

ArrayList это классический массив, который может расширяться в момент выполнения программы. В его основе лежит обычный массив: его размер при создании 10 элементов (по документации, «initial capacity of ten»). Когда место кончается, емкость увеличивается: в OpenJDK новый массив примерно в полтора раза больше старого. Правила, по которым работает ArrayList:

• Так же, как и статический массив, индексируется с 0;
• Вставка в конец и доступ по индексу очень быстрые: O(1);
• Чтобы вставить элемент в начало или середину, понадобится скопировать все элементы на одну ячейку вправо, а затем вставить новый элемент на необходимую позицию;
• Доступ по значению зависит от количества элементов: O(n);
• В отличие от классического массива, может хранить null;

В случае с LinkedList все немного сложнее: в его основе лежит двусвязный список. То есть структурно этот динамический массив Java представляет из себя некоторое количество разбросанных объектов, которые ссылаются друг на друга. Легче объяснить на рисунках. Внутри LinkedList у нас есть главный объект (на схемах он подписан Head; в исходниках JDK эти поля лежат прямо в объекте самого списка), который хранит информацию о количестве элементов, а также ссылку на первый и последний элементы: Сейчас поле size = 0, а first и last = null. Каждый элемент, который добавляется в этот список, это содержимое отдельного внутреннего объекта. Давай добавим элемент Johnny: Теперь у нас появилась нода со значением “Johnny”. У главного элемента ссылки на первый и последний элемент указывают на новую ноду. У этого объекта также есть ссылки на предыдущий и следующий элементы. Ссылка на предыдущий у него всегда будет null, так как это первый элемент, а ссылка на следующий тоже null, потому что его пока нет. Давай это исправим: Добавлен новый элемент, со значением “Watson”, который стал вторым. Следует обратить внимание, что у первого элемента поле next указывает на следующий элемент, а у нового поле previous указывает на предыдущий. У главного элемента ссылка на последний элемент указывает теперь на новую ноду. На следующей схеме показан принцип добавления элементов в середину списка: Был добавлен новый элемент “Hamish”. Чтобы вставить его в середину списка, достаточно переприсвоить ссылки на элементы, как показано на рисунке. Данные иллюстрации объясняют процесс работы двусвязного списка на верхнем уровне, не вдаваясь в подробности. Подводя итог рассказу о LinkedList, можно вывести несколько правил его работы:

• Так же, как и массив, индексируется с 0;
• Доступ к первому и последнему элементу не зависит от количества элементов: O(1);
• Получение элемента по индексу, вставка или удаление из середины списка зависят от количества элементов: O(n);
• Можно использовать механизм итератора: тогда вставка и удаление будут происходить за константное время;
• В отличие от классического массива, может хранить null.

ArrayList и LinkedList рядом

Сведем правила обоих классов в одну таблицу:

Примеры кода

Пройдемся немного по примерам. Фрагменты кода включают в себя примеры как для ArrayList, так и для LinkedList.

Создание

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

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

Добавление элемента

// Новый элемент добавляется в конец
arrayList.add("Johnny");
// Новый элемент добавляется в указанную позицию (в данном случае в начало)
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(). С Java 21 (JEP 431) методы addFirst, addLast, getFirst, getLast, removeFirst и removeLast появились и у ArrayList: их получил сам интерфейс List через новый интерфейс SequencedCollection, так что разница между двумя классами здесь стерлась.

Удаление элемента

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

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

Если происходит удаление объекта по индексу, метод возвращает удаленный объект. Если объект удаляется по значению (remove(Object), а у LinkedList еще removeFirstOccurrence и removeLastOccurrence), метод возвращает true, если объект найден и удален, и false в ином случае. А вот removeFirst(), removeLast() и remove() без аргументов по документации возвращают сам удаленный элемент, а на пустом списке бросают NoSuchElementException.

Доступ к элементу и поиск в списке

// Доступ к элементу по индексу
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);
}

Обратите внимание на второй цикл: для LinkedList обход через get(i) обходится в O(n²), потому что каждый get заново идет по ссылкам от начала или конца списка. Для него используйте for-each или итератор, как в двух последних циклах. Здесь стоит сказать пару слов о поиске. Многие начинающие разработчики при поиске элемента в списке начинают поиск в цикле, сравнивая все элементы с искомым, несмотря на наличие методов indexOf() и lastIndexOf(). Также можно использовать метод contains() для получения факта наличия элемента в списке:

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

Вопросы и ответы

Что такое динамический массив в Java простыми словами?

Это массив, размер которого можно менять во время работы программы. Обычный массив создается с фиксированной длиной: new int[10] навсегда вмещает десять элементов. Динамический массив прячет внутри такой же обычный массив, но при заполнении сам создает новый, побольше, и переносит в него данные. В Java это класс ArrayList из java.util.

Чем ArrayList отличается от LinkedList и что выбрать?

ArrayList хранит элементы в массиве: доступ по индексу мгновенный, вставка в середину требует сдвига хвоста. LinkedList хранит цепочку узлов со ссылками друг на друга: вставка и удаление у концов или через итератор мгновенные, зато доступ по индексу требует обхода по ссылкам, а каждый элемент занимает отдельный объект с двумя ссылками. По умолчанию берите ArrayList: он компактнее и почти во всех сценариях быстрее. LinkedList уместен как очередь или стек (интерфейс Deque) и там, где вставки и удаления идут через итератор.

Как ArrayList увеличивает размер?

Внутри лежит массив с запасом, его размер называется емкостью (capacity). По умолчанию емкость 10. Когда место кончается, создается новый массив (в OpenJDK примерно в полтора раза больше), и старые элементы копируются в него через нативный System.arraycopy. Поэтому добавление в конец в среднем стоит O(1), а отдельные добавления дороже. Если размер известен заранее, задайте его в конструкторе: new ArrayList<>(100000), и копирований не будет.

Можно ли хранить примитивы в ArrayList?

Напрямую нет: списки хранят только объекты, поэтому пишут ArrayList<Integer>, а не ArrayList<int>. Примитив при добавлении автоматически упаковывается в обертку (int в Integer), а при чтении распаковывается обратно. Это удобно, но каждый элемент становится отдельным объектом, так что для миллионов чисел обычный int[] заметно экономнее и быстрее.

Как узнать длину динамического массива?

Методом size(): list.size() возвращает количество элементов. Поля length, как у массива, у списка нет, а метод length() есть только у строк. Текущую емкость внутреннего массива ArrayList узнать нельзя, наружу она не показывается; можно лишь заранее увеличить ее через ensureCapacity(n) или ужать до размера через trimToSize().

Как превратить обычный массив в ArrayList и обратно?

Из массива в список: new ArrayList<>(Arrays.asList(array)) или, с Java 9, new ArrayList<>(List.of(array)). Сам по себе Arrays.asList(array) дает список фиксированного размера поверх того же массива: элементы менять можно, добавлять нельзя. Из списка в массив: list.toArray(new String[0]), а с Java 11 короче list.toArray(String[]::new). Для примитивов это не работает: Arrays.asList(intArray) даст список из одного элемента-массива, нужен Arrays.stream(intArray).boxed().toList().

Ссылки на дополнительное чтение

1. Вот тут есть отличная статья про удаление элементов из ArrayList. За счет того, что это динамический массив Java, есть много тонкостей в удаление элементов.
2. Здесь подробно иллюстрирована работа ArrayList.
3. Немного подробнее о LinkedList.
4. Обзор Java Collections Framework: где ArrayList и LinkedList живут среди остальных коллекций.
5. Пара статей с хабра об ArrayList и LinkedList.