Коллекции в Java. Часть 5.

Интерфейс List и его реализации — ArrayList и LinkedList.

List – интерфейс, который традиционно рассматривают первым и которым пользуются чаще всего.

Название переводится как «список»: интерфейс представляет собой упорядоченную коллекцию данных, похожую на массив. Это значит, что у его элементов есть порядковые номера, показывающие их расположение в списке, – индексы. Но, в отличие от массива, List динамический, о чем я говорил выше, — в нем можно изменять количество элементов.

Интерфейс List имеет две стандартные реализации — ArrayList и LinkedList.

Смысл в том, что можно написать и другие реализации, но в JDK уже есть две, которые доступны «‌‎из коробки».

ArrayList содержит внутри себя массив, длина которого будет увеличиваться автоматически при добавлении в него новых элементов.

Вторая имплементация интерфейса List — класс LinkedList. Это список с двумя связями, где каждый элемент содержит ссылку на предшествующий и следующий элементы списка. Только у первого элемента ссылка на предшествующий элемент будет null, и ссылка у последнего элемента коллекции на следующий элемент будет тоже null, что вполне логично, согласны?

Методы у них одинаковые, но действия с такими списками различаются сложностью выполнения и скоростью.

Методы add() и remove() в связанном списке LinkedList имеют фиксированную скорость выполнения, поэтому оптимальнее. А вот обращение к элементу по индексу быстрее в ArrayList.

👩‍💻 Наш практический курс Java–разработчика

✅ JavaStart. Подписаться

Коллекции в Java. Часть 6.

Vector и его потомок Stack.

Есть еще две реализации, о которых говорят реже. Это Vector и его потомок Stack. Vector похож на ArrayList, но сейчас им не рекомендуют пользоваться — он синхронизированный, за счет этого более потокобезопасный, но менее производительный. Исключение — редкие ситуации с высокими требованиями к потоковой безопасности.

Stack — это стек, работающий по принципу LIFO (last in, first out). Доступ начинается с того элемента, который добавлен в структуру последним, как взятие верхней карты из колоды. Его же быстрее всего можно удалить. Для просмотра последнего элемента есть метод peek(), для просмотра с удалением — pop(), а для добавления элемента в конец — push().

👩‍💻 Наш практический курс Java–разработчика

✅ JavaStart. Подписаться

Коллекции в Java. Часть 7.

Set и его реализации.

Set, или набор, — это математическое множество, реализованное в языке программирования. Если проще, это коллекция уникальных значений. Ни одно из них не повторяется в рамках одного сета.

Для проверки равенства у такой коллекции есть специальный метод equals().

Коллекция не упорядочена, то есть у ее элементов нет порядковых номеров и четких позиций следования. Это может понадобиться при хранении разных структур данных, например имен пользователей сайта: никнеймы уникальны, а порядковых номеров у них нет.

У Set есть два дочерних интерфейса SortedSet и NavigableSet — соответственно, отсортированный и навигируемый сеты. Фактических реализаций три, и о них стоит поговорить подробнее.

Здесь будет посложнее для понимания)

Часто используется реализация HashSet — это сет или множество, которое не позволяет хранение одинаковых элементов благодаря содержанию в себе объекта HashMap. Он использует для хранения данных хэш-таблицы. Хэш-таблица реализована с помощью HashMap — одной из реализаций интерфейса Map, о котором мы поговорим позже.

LinkedHashSet — множество, подобное HashSet, в котором элементы объединены между собой в порядковый список. В этом случае элементы хранятся в том же порядке, в котором и добавляются (благодаря содержанию в себе объекта LinkedHashMap).

TreeSet — коллекция, которая использует для хранения элементов упорядоченное по значениям дерево. TreeSet содержит в себе TreeMap — коллекцию, которая использует для хранения своих элементов сбалансированное красно-черное бинарное дерево. Благодаря этому операции add, remove и contains в этой коллекции очень быстрые (относительно алгоритмической сложности). А это — весомое преимущество по сравнению с другими имплементациями интерфейса Set.

👩‍💻 Наш практический курс Java–разработчика

✅ JavaStart. Подписаться

Коллекции в Java. Часть 8.

Третий прямой наследник Collection — очередь, или Queue и его реализации.

Очередь и стек — два похожих формата, которые различаются принципом доступа к элементам.

Если в стеке мы имеем быстрый доступ к последним добавленным частям, то в очереди — к тем, которые были добавлены первыми. Такой принцип называется FIFO (first in, first out) и действительно напоминает живую очередь.

Соответственно, быстро получить и удалить элемент можно из начала очереди, а добавить — только в ее конец.

У Queue две основных реализации. Одна из них — PriorityQueue, прямая реализация, которая по умолчанию сортирует элементы в порядке их появления в очереди. Но это можно переопределить в конструкторе — специальном методе для создания объекта. Там можно задать связь с интерфейсом Comparator, который будет сравнивать элементы очереди и располагать их в зависимости от значений.

Вторая реализация чуть сложнее. У Queue есть потомок под названием Deque (читается как «дек»). Он расширяет Queue и добавляет возможность создавать коллекции, работающие по принципу LIFO — мы говорили о нем выше. По сути, получается двунаправленная очередь. Так вот вторая реализация называется ArrayDeque и технически является реализацией интерфейса Deque, а не Queue. Но Deque — потомок Queue, так что ArrayDeque периодически называют реализацией Queue.

Упомянутый выше LinkedList — реализация, принадлежащая не только List, но и Deque.

В целом, Queue редко используется, достаточно знать, что это и в чем ее суть, чтобы упомянуть это при рассказе на собеседовании о коллекциях в целом.

👩‍💻 Наш практический курс Java–разработчика

✅ JavaStart. Подписаться