java - 从 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)。