Java合并O(1)中的2个集合

Question

我需要能够将2个大型集合合并到1.我可以使用哪种集合类型？我不需要随机访问各个元素.通常我会选择一个链表,但是我不能将Java中的2个链表与O(1)的运行时合并,这可以在许多其他语言中完成,因为我必须将每个元素复制到新的列表中.

编辑:谢谢你的所有答案.你的答案都非常有用,我设法完成了工作.下次我将使用自己的链接列表实现开始.

Answer 1

您可以Iterable使用Guava的Iterables.concat方法之一在O(1)中创建连接视图:

Iterable<T> combined = Iterables.concat(list1, list2);

这将允许您将两个列表的所有元素作为一个对象进行迭代,而无需复制任何元素.

Answer 2

这里最简单的解决方案是列表清单.意味着您需要一些简单的包装函数,但并不复杂.

Answer 3

理论上,您可以在O(1)中合并2个链接列表,因为您所要做的就是将第一个节点指向第二个节点(假设您有这些参考).

该addAll集合的方法似乎暗示O(n)的运行时间,因为他们都在谈论迭代器.细节可能是特定于JVM的......

我不认为有任何集合将在O(n)中组合.你可能不得不自己动手.