Представим, что у нас есть корзинка с котиками. Мы можем положить котика в корзинку с любой стороны: либо слева, либо справа. И мы можем взять котика из корзинки тоже с любой стороны, не трогая других котиков.
Deque тут представлен в виде корзинки. Он тоже позволяет удобно добавлять и удалять котиков данные с обеих сторон. Т.е. это такая структура, которая объединяет в себе возможности стека и очереди.
В котлин есть несколько реализаций. У каждой свои особенности и преимущества. Чаще всего используются ArrayDeque и LinkedList. ArrayDeque сегодня и рассмотрим.
В самом интерфейсе достаточно много методов на любой запрос и вкус. На всякий случай покажу:
ArrayDeque
ArrayDeque основан на массиве и обеспечивает быстрое добавление и удаление элементов слева и справа. Он идеально подходит для ситуаций, когда заранее известно максимальное количество котиков или когда требуется высокая производительность при частом добавлении/удалении (НЕ в середину).
Немного информации из документации:
- ArrayDeque не имеет ограничения по размеру. Он автоматически увеличивается по мере необходимости. По умолчанию создаётся с количеством в 16 элементов.
- ArrayDeque не потокобезопасный. Это значит, что не стоит взаимодействовать с ArrayDeque одновременно из разных потоков без какой-либо синхронизации.
- В ArrayDeque нельзя добавлять элементы со значением null.
- ArrayDeque скорее всего будет работать быстрее, чем Stack, когда используется как стек, и быстрее, чем LinkedList, когда используется как очередь (это прям цитата из документации).
- Итераторы, возвращаемые ArrayDeque, являются "fail-fast". Это значит, что если дек изменяется после создания итератора любым образом не через метод этого итератора, то итератор будет генерировать ConcurrentModificationException.
Простое объяснение этого пункта: в ArrayDeque есть специальная "функция безопасности" для итераторов, которая называется "fail-fast". Это значит, что если мы начали считать котиков с помощью итератора, и в это время кто-то другой добавил/удалил котика и изменил дек, то итератор обидится и сразу же сообщит об ошибке, выбросив ConcurrentModificationException.
Добавление элементов:
- Когда добавляется элемент, он помещается либо в начало, либо в конец массива, в зависимости от операции. Если массив заполнен, создаётся новый большего размера, и элементы копируются в него.
- Расширение происходит путём удвоения текущей емкости плюс 1 (если текущая емкость меньше 64 элементов) или увеличения на 50% (если текущая емкость 64 и более) (https://github.com/openjdk/jdk/blob/9d764ee48ee7c2e7be7a25aee2ed7bed2fcd2000/src/java.base/share/classes/java/util/ArrayDeque.java#L140). Этот процесс называется реаллокацией (ставь лайк, если тоже впервые узнал про это слово), и он включает в себя создание нового массива большего размера и перенос элементов из старого массива в новый.
Удаление элементов:
- При удалении элемента, индексы для начала и конца дека обновляются. Если элементов стало совсем мало, то размер может автоматически уменьшиться.
- Уменьшение размера обычно происходит, когда количество элементов в деке становится меньше четверти от размера массива (я не нашла доказательств, но пишут так).
- При уменьшении размер массива обычно устанавливается в два раза больше текущего количества элементов, но не меньше начального размера массива (обычно 16 элементов). Потом элементы копируются в новый массив.
Сложность:
- Добавление/удаление элементов в начале/конце (addFirst/addLast, removeFirst/removeLast):
LinkedList: O(1). Операции не требуют прохода по списку.
ArrayDeque: O(1). Амортизированное константное время (O(1)). Операции быстрые, но иногда требуется расширение или сжатие массива. - Добавление/удаление элементов из середины:
LinkedList: O(n) для доступа (если не используется итератор).
Если у нас есть итератор на конкретный элемент, то добавление и удаление через него будет O(1).
ArrayDeque: O(n). Требуется сдвиг элементов для поддержания непрерывности массива. - Доступ к элементам (getFirst, getLast):
LinkedList: O(1). Прямой доступ к первому и последнему элементам.
ArrayDeque: O(1). Прямой доступ к элементам на основе индексов в массиве. - Доступ к элементу по индексу (get(index)):
LinkedList: O(n). Требуется проход по списку для достижения элемента с заданным индексом.
ArrayDeque: O(1). Быстрый доступ благодаря индексации массива.
Дубль статей в телеграмме — https://t.me/android_junior
Мои заметки в телеграмме — https://t.me/android_junior_notes
P.S. сделано с помощью ChatGPT и Midjourney