用Java在常量时间内合并两个列表
有谁知道是否可以在Java中定时合并两个列表（或任何集合）？
http://www.cppreference.com/wiki/stl/list/splice
在C中使用链接列表很容易
谢谢，
就我所知，JDK库中的类不支持这一点。
如果您构建自己的List实现（您可以自由执行），那么这是完全合法的。 您可以使用LinkedList并识别要添加的集合也是LinkedList的特例。
在记录你的课程时，你需要指出添加的对象成为新对象的一部分，换句话说，失去了很多普遍性。 还有很多错误的可能性：在加入之后更改原始列表（如果它们是可变的）将允许您创建一个列表，其中有一个空格或两个尾部。 另外，大多数其他操作不会从您的黑客入侵课程中受益。 换句话说，乍一看，这似乎是一个疯狂的想法。
请注意，“合并”列表通常具有不同的内涵; 例如，当合并排序列表时，可以期望结果列表具有相同的排序。 你在谈论加入两个链接列表时真的更好地称为“拼接”。 或者也许只是“加入”。
你可以在多个List的周围实现一个复合“包装器”。 为了简单起见，我使我的示例不可变，但是您始终可以实现add以追加到存储在组合对象内的“最终” List 。
public class CompositeImmutableList<T> implements List<T> {
private final List<T> l1;
private final List<T> l2;
public CompositeImmutableList(List<T> l1, List<T> 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.
}
您可以执行下一步：在此处获取Java源代码的LinkedList：LinkedList.java
然后在这个实现中添加下一个函数：
public void concatenate(LinkedList<E> 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将在末尾添加参数LinkedList，最后两个LinkedList的头将指向第一个和最后一个元素。 在这种方法中，我不在意这两个列表中的哪一个是空的，因此在使用它之前请确保您有两个元素列表，否则您必须检查并注意这一点。
测试1：
public static void main(String[] args)
{
LinkedList<String> test1 = new LinkedList<String>();
LinkedList<String> test2 = new LinkedList<String>();
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<String> test1 = new myutil.LinkedListExt<>();
myutil.LinkedList<String> test2 = new myutil.LinkedListExt<>();
test1.add("s1");
test1.add("s2");
test2.add("s3");
test2.add("s4");
for (int i=0; i<count; ++i)
test2.add("s");
long start = System.nanoTime();
test1.concatenate(test2);
long elapsedTime = System.nanoTime() - start;
System.out.println(elapsedTime/1000000.0);
java.util.LinkedList<String> test3 = new java.util.LinkedList<>();
java.util.LinkedList<String> test4 = new java.util.LinkedList<>();
test3.add("s1");
test3.add("s2");
test4.add("s3");
test4.add("s4");
for (int i=0; i<count; ++i)
test4.add("s");
start = System.nanoTime();
test3.addAll(test4);
elapsedTime = System.nanoTime() - start;
System.out.println(elapsedTime/1000000.0);
}
出：
0.004016
10.508312