从 ArrayDeque 获取元素的时间复杂度

Question

我在某些地方读到 Java 中的 LinkedList 添加和删除元素的时间复杂度为 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)。

编辑：

摊销的恒定时间操作意味着大部分时间的操作成本将是 O(1)，除了可能在某些情况下，例如。当 ArrayDeque 需要调整大小时。ArrayDeque 的 javadoc 也说，

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

因此，每当将新元素添加到 ArrayDeque 的末尾或开头时，其大小都会发生变化 -> 因此，如果元素总数违反了 ArrayDeque 的容量属性，则需要调整其大小，这可能高于 O(1 ）。但是如果你做很多这样的操作并平均时间复杂度，它会非常接近 O(1)。