SequencedCollection и SequencedSet

3 ноября 2023

Тэги: Collections, Java, алгоритмы, ООП.

Содержание

SequencedCollection
Добавление первого и последнего элемента
Чтение первого и последнего элемента
Удаление первого и последнего элемента
Производительность
SequencedSet
Выводы

SequencedCollection

В Java 21 появилась новая группа интерфейсов коллекций, самым основным из которых является SequencedCollection. Он расширяет базовый интерфейс Collection, добавляя в него ряд полезных методов для манипуляций с первым и последним элементами, а также для инвертирования коллекции:

interface SequencedCollection<E> extends Collection<E> {
    void addFirst(E e);
    void addLast(E e);
    E getFirst();
    E getLast();
    E removeFirst();
    E removeLast();
    SequencedCollection<E> reversed();
}

Две основных реализации интерфейса List (ArrayList и LinkedList) также поддерживают этот интерфейс.

Иерархия интерфейсов и классов SequencedCollection

Добавление первого и последнего элемента

С помощью методов addFirst() и addLast() мы можем добавлять элементы в начало и конец списка. По сути метод addLast() эквивалентен часто используемому методу add():

SequencedCollection<Integer> list = new ArrayList<>();
for (int i = 0; i < 10; i++) {
list.addLast(i); // эквивалент add()
}

Чтение первого и последнего элемента

Методы getFirst() и getLast() позволяют просматривать первый и последний элементы списка. Но если список пустой, то мы получим исключение NoSuchElementException:

System.out.println(list.getFirst()); // 0
System.out.println(list.getLast()); // 9

list.addFirst(-1);
System.out.println(list.getFirst()); // -1

Collections.emptyList().getFirst(); // NoSuchElementException

Так же легко мы можем вывести содержимое списка в обратном порядке с помощью метода reversed():

System.out.println(list.reversed());
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1]

Удаление первого и последнего элемента

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

SequencedCollection<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.removeFirst();
list.removeLast();
System.out.println(list); // [2, 3]

list.clear();
list.removeFirst(); // NoSuchElementException

При попытке удалить элемент из пустого списка получаем исключение.

Производительность

Теперь пара слов о производительности. Получив столь удобные методы, легко забыть, какие действия происходят «под капотом».

Операции чтения первого и последнего элемента, а также операции добавления и удаления в конец списка в обоих реализациях ArrayList и LinkedList происходят мгновенно. А вот добавление и удаление первого элемента в ArrayList гораздо медленее, чем в LinkedList. Это связано с их внутренней реализацией. Более подробно про эти структуры данных см. в статье Коллекции: list, set, map.

Добавление в начало с помощью addFirst() в LinkedList требует изменение пары-тройки ссылок (все элементы остаются на своих местах, а слева к ним присоединяется ещё один), что происходит мгновенно. Тогда как в ArrayList нам нужно сначала сдвинуть ВСЕ элементы массива вправо, чтобы появилось место для первого элемента. Эта операция хорошо оптимизирована, но для больших списков (миллионы элементов) может вносить уже заметную задержку.

То же относится и к removeFirst() в ArrayList. Мы должны сдвинуть ВСЕ элементы влево, начиная со второго.

Поэтому если часто добавляете или удаляете первый элемент – выбирайте LinkedList.

SequencedSet

Частным случаем SequencedCollection является интерфейс SequencedSet. При этом он лишь переопределяет унаследованный метод reversed(), возвращая не SequencedCollection, а сам SequencedSet.

interface SequencedSet<E> extends SequencedCollection<E>, Set<E> {

SequencedSet<E> reversed();
}

Этот интерфейс реализуют классы LinkedHashSet (сохраняет порядок добавления) и TreeSet (сортирует в алфавитном порядке). При этом HashSet данный интерфейс не поддерживает, т.к. не обеспечивает порядок.

Иерархия интерфейсов и классов SequencedSet

В остальном всё, что мы рассмотрели выше для списков, справедливо и для множеств:

SequencedSet<Integer> numbers = new LinkedHashSet<>();
numbers.addFirst(1);
numbers.addLast(2); // аналог add()
numbers.addLast(3);
numbers.addFirst(1); // не будет добавлено, т.к. такое значение уже есть

System.out.println(numbers); // [1, 2, 3]
System.out.println(numbers.reversed()); // [3, 2, 1]

numbers.removeLast();
numbers.removeFirst();
System.out.println(numbers); // [2]

В отличие от LinkedHashSet, класс TreeSet хоть и поддерживает интерфейс SequencedSet, но не поддерживает методы addFirst() и addLast(). Вместо них по-прежнему добавляем элементы через add(). И это логично, т.к. TreeSet сам решает какой элемент должны быть «первым» и какой «последним».

SequencedSet<Integer> numbers = new TreeSet<>();
numbers.add(2); // addFirst() и addLast() не поддерживаются
numbers.add(3);
numbers.add(1);

System.out.println(numbers); // [1, 2, 3]
System.out.println(numbers.reversed()); // [3, 2, 1]

При этом удаление первого и последнего элемента из TreeSet возможно:

numbers.removeLast();
numbers.removeFirst();
System.out.println(numbers); // [2]

Выводы

Мы рассмотрели интерфейс SequencedCollection и его наиболее распространённые реализации ArrayList и LinkedList. Научились добавлять и удалять первый и последний элементы, а также инвертировать упорядоченную коллекцию. Узнали какая реализация лучше подходит для работы с методом addFirst().

Также познакомились с более частным интерфейсом SequencedSet и особенностями его реализации в классах LinkedHashSet и TreeSet.

Облако тэгов

Kotlin, Java, Spring, Spring Boot, Spring Data, SQL, PostgreSQL, Oracle, Linux, Hibernate, Collections, Stream API, многопоточность, файлы, Nginx, Apache, maven, gradle, JUnit, YouTube, новости, руководство, ООП, алгоритмы, головоломки, rest, GraphQL, Excel, XML, json, yaml.