在Java中以恒定时间合并两个列表

有谁知道在Java中是否可以在常量时间内合并两个列表（或任何集合）？

http://www.cppreference.com/wiki/stl/list/splice

使用C中的链接列表很容易做到这一点…

谢谢，

Answer 1

据我所知，JDK库中的类不支持这一点。

如果您构建自己的List实现是可能的 – 您可以自由地执行它，这是完全合法的。 您可以使用LinkedList并识别要添加的集合也是LinkedList的特殊情况。

在记录你的类时，你需要指出添加的对象成为新对象的一部分，换句话说，很多普遍性都会丢失。 还有很多可能出错的地方：在加入之后更改原始列表中的任何一个（如果它们是可变的）将允许您创建一个带有间隙或两个尾部的列表。 此外，大多数其他操作不会受益于您的黑客攻击类。 换句话说，乍一看似乎是一个疯狂的想法。

请注意，“合并”列表通常具有不同的含义; 例如，当合并排序列表时，可以预期结果列表具有相同的排序。 你加入两个链接列表时所说的最好被称为“拼接”。 或者只是“加入”。

Answer 2

您可以围绕多个List实现Composite“包装器”。 为简单起见，我使我的示例不可变，但您可以始终实现add以附加到复合对象中存储的“最终” List 。

 public class CompositeImmutableList implements List { private final List l1; private final List l2; public CompositeImmutableList(List l1, List l2) { this.l1 = l1; this.l2 = l2; } public boolean add(T t) { throw new UnsupportedOperationException(); } public int size() { return l1.size() + l2.size(); } public T get(int i) { int sz1 = l1.size(); return i < s1 : l1.get(i) : l2.get(sz1 - i); } // TODO: Implement remaining List API methods. } 

Answer 3

您可以执行以下步骤：在此处获取Java源的LinkedList： LinkedList.java

然后通过这个实现添加下一个函数：

 public void concatenate(LinkedList list) { header.previous.next = list.header.next; list.header.next.previous = header.previous; list.header.previous.next = header.next; header.next.previous = list.header.previous; list.header.next = header.next; header.previous = list.header.previous; size = size + list.size; modCount = modCount + list.modCount + 1; list.size = size; list.modCount = modCount; } 

使用此代码，2 LinkedList将是相同的LinkedList，因此您将合并为一个。 容器LinkedList将在末尾添加param LinkedList，最后LinkedList的头部将指向第一个和最后一个元素。 在这个方法中，我不关心两个列表中的一个是否为空，因此在使用它之前确保你有两个包含元素的列表，否则你必须检查并注意这一点。

测试1：

 public static void main(String[] args) { LinkedList test1 = new LinkedList(); LinkedList test2 = new LinkedList(); test1.add("s1"); test1.add("s2"); test2.add("s4"); test2.add("s5"); test1.concatenate(test2); System.out.println(test1); System.out.println(test2); } 

出：

 [s1, s2, s4, s5] [s1, s2, s4, s5] 

Test2性能：

 public static void main(String[] args) { int count = 100000; myutil.LinkedList test1 = new myutil.LinkedListExt<>(); myutil.LinkedList test2 = new myutil.LinkedListExt<>(); test1.add("s1"); test1.add("s2"); test2.add("s3"); test2.add("s4"); for (int i=0; i test3 = new java.util.LinkedList<>(); java.util.LinkedList test4 = new java.util.LinkedList<>(); test3.add("s1"); test3.add("s2"); test4.add("s3"); test4.add("s4"); for (int i=0; i 

出：

 0.004016 10.508312 

Answer 4

如果用C中的链表很容易，那么我猜想LinkedList类提供了相同的性能

对于双向链表，所有操作都可以预期。 索引到列表中的操作将从开头或结尾遍历列表，以较接近指定索引为准。

 List list1 = new LinkedList(); list1.add(...); List list2 = new LinkedList(); list2.add(...); list1.addAll(list2); 

编辑：没关系。 看起来LinkedList.addAll（Collection）调用LinkedList.addAll（int，Collection），它遍历新集合。