java - 为什么没有 LinkedList.join() 方法来在 O(1) 时间内合并两个未排序的列表？

Question

我不是数据结构专家，但据我了解，链表已被证明在大多数情况下效率相当低，主要是由于缓存未命中。我考虑使用它们的少数原因之一是在恒定时间内合并/拆分其中两个的独特能力；但该类没有提供这样的方法。

我想，好吧，我会实现自己的以满足我的需求。我希望新类遵循 Collections 框架 API，因此我让它实现并扩展了与标准 LinkedList 完全相同的类。很快我意识到我只是重新创建 LinkedList 而这一切都是毫无意义的。那时我不妨复制粘贴代码并添加我需要的方法。

同样，我找不到没有这样一种方法的原因(也许除了我还远没有完全掌握的线程安全性)。一切看起来都像一个标准的链表实现，并且类似于 C++ STL 中的 splice() 的方法可以适合其中。

我错过了什么吗？

LinkedList<Integer> list1 = new LinkedList();
list1.add(4); 
list1.add(2);
list1.add(7);
// list1 = {4 , 2 , 7}

LinkedList<Integer> list2 = new LinkedList();
list2.add(9);
list2.add(4);
list2.add(6);
// list2 = {9 , 4 , 6}

list1.join(list2); // in O(1)
// at this point list2 should be invalidated/empty
// list1 = {4 , 2 , 7 , 9 , 4 , 6}
// list2 = {}

Answer 1

Java 的原生链表实现存在问题。无法在列表内或列表之间移动节点，与 C++ std::list::splice() 不等效。如果在链表中的任何位置插入或删除节点，则链表的所有迭代器都会失效，但使用迭代器参数完成删除的情况除外，在这种情况下，除了用于执行删除操作的迭代器之外的所有迭代器插入或删除均无效。迭代器不能进行浅复制，赋值只是将目标迭代器指向源迭代器所指向的同一个迭代器对象。

这些问题使得合并或合并排序等操作变得困难，对于基于迭代器的操作来说更是如此。

对于 Visual Studio C++ std::list，删除节点只会使已删除节点的迭代器无效，并且仅在调试版本中。在发布版本中，没有迭代器会失效，并且由程序员负责确保删除的节点不会导致迭代器指向已删除的对象。

---

至于为什么 Java 的原生链表有这些限制，Sun 当时声明的原因是他们想要一个“紧凑的框架”，而不是与 C++ 保持一致，C++ 比 Java 集合早 4 年(1998 年 Java 集合，1994 年 HP 版权)对于 Visual Studio 2005 和早期版本的 Microsoft 及其他 C++ 编译器，大多数或所有 STL 包含文件末尾显示的日期。尽管事实上集合的前身之一 JGL 确实有与 C++ 保持一致的目标。

https://en.wikipedia.org/wiki/Java_collections_framework#History

还有其他对 Java 的批评，例如没有无符号整数、以不同的方式对待基元和对象、对基元的操作集有限等等。