Динамические структуры данных java

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

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

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

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

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

Динамический массив — это массив, который умеет изменять свой размер во время выполнения программы. В Java эту роль играют в основном классы ArrayList и LinkedList. В отличие от массивов, ArrayList и LinkedList содержат только ссылочные типы данных, то есть сохранить в них можно только объекты. К счастью, в 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 for(int i = 0; i // Использование цикла for-each for(String s : arrayList) < System.out.println(s); >for(String s : linkedList)

Здесь стоит сказать пару слов о поиске. Многие начинающие разработчики при поиске элемента в списке начинают поиск в цикле, сравнивая все элементы с искомым, несмотря на наличие методов indexOf() и lastIndexOf() . Также можно использовать метод contains() для получения факта наличия элемента в списке:

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

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

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

Источник