在 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屋！