Реализация интерфейсов List и Deque в Java, представляющая собой двусвязный список. Каждый узел (Node) содержит ссылки на предыдущий и следующий элементы, а также данные.
Особенности:
- Вставка/удаление: Эффективно вставлять или удалять элементы в любом месте списка (O(1)), так как требуется лишь изменить ссылки у соседних узлов.
- Произвольный доступ: Доступ к элементу по индексу (get) или поиск элемента (indexOf) требуют обхода списка с начала или конца, что занимает время пропорционально положению элемента (O(n)).
- Использование памяти: Требует больше памяти по сравнению с
ArrayList, так как каждый узел хранит две ссылки в дополнение к данным.
- Null-элементы: Позволяет хранить
null.
- Потокобезопасность: Не является потокобезопасным по умолчанию.
Применение:
- Реализация очередей и стеков, где часто выполняются операции добавления/удаления с начала или конца.
- Сценарии, где требуется частая модификация списка (вставка/удаление) в произвольных позициях.
Пример:
java