Java在O（1）合并2个集合
我需要能够将2个大集合合并为1.哪种集合types最适合我？ 我不需要随机访问各个元素。 通常我会去找一个链表，但是我不能将2个链表在Java中与O（1）的运行时相结合，这可以用其他语言来完成，因为我必须将每个元素复制到新列表中。
编辑：谢谢你的答案。 你的回答都非常有帮助，我设法完成了工作。 下一次，我将使用我自己的实现一个链接列表开始。
您可以使用Guava的Iterables.concat方法之一在O（1）中创build一个串联的Iterable视图：
Iterable<T> combined = Iterables.concat(list1, list2);
这将允许您迭代两个列表的所有元素作为一个对象，而不复制任何元素。
这里最简单的解决scheme确实是列表清单。 意味着你需要一些简单的包装函数，但没有什么复杂的。
理论上，你可以在O（1）中合并2个链表，因为你所要做的就是把第一个节点的第一个节点指向第二个节点（假设你有这些引用）。
收集的addAll方法似乎意味着O（n）的运行时间，因为他们正在谈论迭代器。 细节可能是特定于JVM的…
我不认为有任何collections品将结合在O（n）中。 你可能不得不推出自己的。
我认为你最好的办法就是创build一个以List>为参数的List的实现，然后委托。 换句话说，有一个清单的列表，并把它们连接起来作为一个清单。 当你通过列表1的元素时，你开始看列表2。
出于某种原因，我认为番石榴有这样一个名单。 但我无法在他们的javadoc中find它。
如果你只想拥有对象集合并在O（1）时间内合并它们，而不介意实现自己的数据结构，那么最简单的方法就是使用不平衡的二叉树：每个节点都是叶（存储一个值）或两棵树的组合，你可以用一个抽象的超类或接口来实现这两个类。 深度优先遍历可以用来提取元素。
这与ColinD的迭代器连接build议基本相同，但是更加简单。
问题是迭代这个集合不会是O（ n ）！ 它将是O（ n + m ），其中m是你已经执行的合并的数量（因为每个是要遍历的节点）。 我的解决scheme和ColinD都是如此。 我不知道这个问题是否可行。
没关系以上。 在这个scheme下，每个合并至less添加一个元素，所以m < n ，所以迭代成本仍然是O（ n ）。 （如果您使用迭代器连接，请确保不频繁连接空迭代器，因为这会增加成本。）
合并链表实际上是O（1），你可以用同样的方式考虑基于数组的列表，例如在它们之间链接多个Object []。
有上面的实现，当从中间/开始移除/插入时比ArrayList快。 迭代实际上是一样的。 随机访问可以稍微慢一些。
我想从apache.commonsbuild议CompositeCollection类，但是看看这个运行在O（n）中的源代码 。 如果您只需要迭代元素而不想按照ColinD的build议使用Google Collections，则可以轻松创build自己的复合迭代器，例如
public class CompositeCollectionIterator<T> implements Iterator<T>{ private Iterator<T>[] iterators; private int currentIteratorIndex = 0; public CompositeCollectionIterator( Collection<T>... aCollections ) { iterators = new Iterator[ aCollections.length]; for ( int i = 0, aCollectionsLength = aCollections.length; i < aCollectionsLength; i++ ) { Collection<T> collection = aCollections[ i ]; iterators[i] = collection.iterator(); } } public boolean hasNext() { if ( iterators[currentIteratorIndex].hasNext() ) return true; else if ( currentIteratorIndex < iterators.length - 1 ){ currentIteratorIndex++; return hasNext(); } return false; } public T next() { return iterators[currentIteratorIndex].next(); } public void remove() { iterators[currentIteratorIndex].remove(); } }
通过使用两个链表作为你的集合，并存储指向每个列表的第一个和最后一个元素的指针（这两个指针在添加/删除项目时可能需要更新），你可以在O（1）中合并这两个列表 – 只需连接第一个列表的最后一个元素添加到第二个列表的第一个元素，并相应地调整第一个/最后一个指针。
恐怕你需要在Java中自己实现链表，因为你没有直接访问LinkedList的底层节点，因此你不能将第一个列表的最后一个元素连接到第二个列表的第一个元素。
幸运的是，在Java中很容易find链表实现，因为它是数据结构课程中一个非常常见的主题。 例如， 这里是一个 – 我知道，名称是西class牙文，但ListaEncadenada （“LinkedList”）和NodoLista （“ListNode”）中的代码非常简单，应该是不言自明的，最重要的是 – 实现包含指向列表的第一个和最后一个元素，并可以很容易地修改，以满足您的需求。
