Сложность времени, чтобы получить элемент из ArrayDeque

Question

В некоторых местах я читал, что LinkedList в Java имеет O (1) сложность по времени для добавления и удаления элементов, но O (n) для получения элементов.И ArrayList имеет O (1) для получения элементов и O (n) для добавления и удаления.

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

Answer 1

Из javadoc написано:

Most ArrayDeque operations run in amortized constant time. Exceptions include remove,
removeFirstOccurrence, removeLastOccurrence, contains, iterator.remove(), and the bulk
operations, all of which run in linear time.

Итак, удаление элемента является линейной операцией по времени, получая его должно быть O (1).

EDIT:

Амортизированная операция с постоянным временем означает, что большую часть времени операционные затраты будут O (1), за исключением, возможно, в некоторых случаях, например.когда ArrayDeque необходимо изменить размер.Javadoc для ArrayDeque также говорит:

Array deques have no capacity restrictions; they grow as necessary to support usage 

Таким образом, всякий раз, когда новые элементы добавляются в конец или начало ArrayDeque, его размер изменяется -> следовательно, если общее количество элементов нарушает свойство ёмкостиArrayDeque, его нужно изменить, что может быть выше, чем O (1).Но если вы выполняете много таких операций и усредняете сложность времени, она будет очень близка к O (1).