Java 集合添加所有复杂性

Question

对于 addAll 操作，是否有复杂度为 O(1) 而不是 O(n) 的 Java 集合，还是必须实现我自己的集合？使用有效的链表，Collection1.addAll(Collection2) 操作应该将第二个集合附加到第一个集合，将 collection2 的第一个节点添加到集合 1 的最后一个节点，然后其他的。但这并不是我阅读了似乎使用迭代器的文档，所以我猜复杂度是 O(collection2.size)。

那正确吗 ？

Answer 1

即使是对链接列表的优化也只有在将项目从一个链接列表移动到另一个链接列表时才起作用。

然而，您可以构建一种自己的集合，它具有更多的间接级别，即包含集合的集合。这样，添加整个集合的成本非常低，迭代也是如此。然而，索引或长度确定可能变得相当昂贵。