在Java中以恒定时间合并两个列表 [英] Merge two lists in constant time in Java

问题描述

有没有人知道是否可以在Java中以恒定时间合并两个列表（或任何集合）？

Does anyone know if it's possible to merge two lists (or any collection) in constant time in Java ?

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

使用C中的链接列表很容易做到...

It's so easy to do that using linked lists in C...

谢谢，

推荐答案

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

The classes in the JDK library don't support this, as far as I know.

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

It's possible if you build your own implementation of List - which you're free to do, it's perfectly legal. You could use LinkedLists and recognize the special case that the collection to be added is also a LinkedList.

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

In documenting your class, you'd need to point out that the added object becomes part of the new object, in other words a lot of generality is lost. There's also lots of potential for error: Altering either of the original lists (if they're mutable) after joining would allow you to create a list with a gap in it, or with two tails. Also, most other operations wouldn't benefit from your hacked-up class. In other words, at first blush it seems like a crazy idea.

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

Note that "merging" lists usually has different connotations; when merging sorted lists, for example, one would expect the resultant list to have the same ordering. What you're talking about with joining two Linked Lists is really better termed as "splicing". Or maybe just "joining."

这篇关于在Java中以恒定时间合并两个列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！