IT-Storm

Существенный минус массивов — статичность: необходимо заранее задавать их размер. Однако программисты пока не умеют предсказывать будущее. По этой причине создали структуру, которая сможет изменять размер в момент работы программы. Она получила название динамический массив.


Что такое динамический массив?
Динамический массив — это массив, который умеет изменять свой размер во время выполнения программы. В 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 arrayList = new ArrayList<>();
// Создается новый список и указывается начальный размер внутреннего массива
ArrayList arrayListLarge = new ArrayList<>(100000);

// Создаем новый LinkedList
LinkedList 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"); 

Подробнее об ArrayList - здесь