为什么没有 LinkedList.join() 方法在 O(1) 时间内合并两个未排序的列表？
Why is there not a LinkedList.join() method to merge two unsorted lists in O(1) time?
我不是数据结构专家，但据我所知，链表在大多数情况下被证明效率很低，主要是由于缓存未命中。我会考虑使用它们的少数几个原因之一是在恒定时间内 merge/split 其中两个的独特能力；但是 class 没有提供这样的方法。
我想，好吧，我会实现我自己的以满足我的需要。我希望新的 class 遵循集合框架 API，所以我让它实现并扩展了与标准 LinkedList 相同的 classes。很快我意识到我只是在重新创建 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 = {}
Java 对本机 linkedlist 的实施存在问题。无法在列表内或列表之间移动节点，不等同于 C++ std::list::splice()。如果在 linked 列表中的任何位置插入或删除节点，link 列表的所有迭代器都会失效，但使用迭代器参数完成删除的情况除外，在这种情况下除了用于插入或删除的迭代器之外的所有迭代器都无效。迭代器不能浅拷贝，赋值只是将目标迭代器指向源迭代器指向的同一个迭代器对象。
这些问题使合并或合并排序等操作变得困难，对于基于迭代器的操作更是如此。
在 Visual Studio C++ std::list 的情况下，删除节点只会使指向已删除节点的迭代器无效，并且仅在调试版本中。在发布版本中，没有迭代器会失效，程序员需要确保删除的节点不会导致迭代器指向已删除的对象。
至于为什么 Java 的原生 linkedlist 有这些限制，Sun 当时声明的原因是他们想要一个“紧凑的框架”而不是与 C++ 一致，C++ 早于 Java 4 年的合集（Java 合集为 1998 年，对于 Visual Studio 2005 年以及 Microsoft 和其他软件的早期版本，大部分或所有 STL 包含文件末尾显示的 HP 版权日期为 1994 年C++ 编译器）。尽管事实上集合的前身之一 JGL 确实有与 C++ 保持一致的目标。
https://en.wikipedia.org/wiki/Java_collections_framework#History
还有其他对 Java 的批评，例如没有无符号整数、以不同方式对待原语和对象、对原语的操作集有限，...
我不是数据结构专家，但据我所知，链表在大多数情况下被证明效率很低，主要是由于缓存未命中。我会考虑使用它们的少数几个原因之一是在恒定时间内 merge/split 其中两个的独特能力；但是 class 没有提供这样的方法。
我想，好吧，我会实现我自己的以满足我的需要。我希望新的 class 遵循集合框架 API，所以我让它实现并扩展了与标准 LinkedList 相同的 classes。很快我意识到我只是在重新创建 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 = {}
Java 对本机 linkedlist 的实施存在问题。无法在列表内或列表之间移动节点，不等同于 C++ std::list::splice()。如果在 linked 列表中的任何位置插入或删除节点，link 列表的所有迭代器都会失效，但使用迭代器参数完成删除的情况除外，在这种情况下除了用于插入或删除的迭代器之外的所有迭代器都无效。迭代器不能浅拷贝，赋值只是将目标迭代器指向源迭代器指向的同一个迭代器对象。
这些问题使合并或合并排序等操作变得困难，对于基于迭代器的操作更是如此。
在 Visual Studio C++ std::list 的情况下，删除节点只会使指向已删除节点的迭代器无效，并且仅在调试版本中。在发布版本中，没有迭代器会失效，程序员需要确保删除的节点不会导致迭代器指向已删除的对象。
至于为什么 Java 的原生 linkedlist 有这些限制，Sun 当时声明的原因是他们想要一个“紧凑的框架”而不是与 C++ 一致，C++ 早于 Java 4 年的合集（Java 合集为 1998 年，对于 Visual Studio 2005 年以及 Microsoft 和其他软件的早期版本，大部分或所有 STL 包含文件末尾显示的 HP 版权日期为 1994 年C++ 编译器）。尽管事实上集合的前身之一 JGL 确实有与 C++ 保持一致的目标。
https://en.wikipedia.org/wiki/Java_collections_framework#History
还有其他对 Java 的批评，例如没有无符号整数、以不同方式对待原语和对象、对原语的操作集有限，...