Ответ
Двусвязный список. Каждый элемент (узел) хранит:
E item— данные.Node<E> next— ссылку на следующий узел.Node<E> prev— ссылку на предыдущий узел.
Внутренний класс узла:
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}| Сложность основных операций: | Операция | Сложность | Примечание |
|---|---|---|---|
| Вставка/удаление в начале/конце | O(1) | Известны ссылки на head и tail. | |
| Вставка/удаление по индексу | O(n) | Требуется линейный обход до позиции. | |
| Получение элемента по индексу | O(n) | Линейный поиск. | |
| Поиск по значению | O(n) | Линейный поиск. |
Память: Занимает больше, чем ArrayList, из-за хранения двух дополнительных ссылок на каждый элемент.