集合在Java中是否有用于链表的快速concat方法？

Question

如何通过jdk1用Java在O（1）中连接两个链表。谷歌或apache commons collection或其他什么？例如，在jdk中，只有addAll方法是O（n）

我错过的另一个功能是合并两个列表，其中每个列表的顺序可能是相反的。为了说明这一点，假设有两个列表a->；b->；c和e->；f->；g可以合并为

1. a->；b->；c->；e->；f->；g
2. a->；b->；c->；g->；f->；e
3. c->；b->；a->；e->；f->；g
4. c->；b->；a->；g->；f->；e

你知道这样一个列表的实现吗？或者我必须实现我自己的链表吗？了解如何调整现有解决方案也会很有帮助（例如，jdk LinkedList只有很多私有方法）。这些特征在我看来非常明显，希望我没有遗漏一些愚蠢的东西

正如米西姆指出的，问题Merge two lists in constant time in Java是相关的，但不是真正的重复！ 现在的问题是：

1. 是否可以使用其他收款LIB
2. 如何求逆

Answer 1

目前我看到的唯一解决方案是实现List，创建一个构造函数，如下所示：

public EnhancedList (List l1, List l2)

并覆盖所有方法。在这样的解决方案中，您是否想要连接LinkedList或任何其他列表实际上并不重要

Answer 2

对于concat，我建议您执行以下操作：

• 确保所有参数/变量都声明为列表<&燃气轮机；不是LinkedList<&燃气轮机
• 更改新的LinkedList<&燃气轮机；(); 到新的ArrayList<&燃气轮机；();
• 配置应用程序
• 更改新的ArrayList<&燃气轮机；到新的LinkedList<&燃气轮机；();
• 配置应用程序

根据您的使用情况，ArrayList可能比LinkedList快得多。另外，通过查看配置文件数据，您可以看到使用addAll对性能的影响有多大——如果没有那么大，请不要费心“修复”它

在某些情况下，你在其他语言方面的经验是不正确的。您可能会发现addAll在Java中满足了您的需求

如果您要编写自己的concatable列表，请确保它符合列表界面，然后更改代码并重新配置它，确保它更快。如果不是，那么就扔掉它，坚持使用标准列表类型

Answer 3

在以下情况下，调整LinkedList以在jdk中获得O（1）concat将起作用：

1. 方法entry（）和变量header和size以及内部类条目将受到保护

2. addAll将检测LinkedList，然后执行以下操作：

   JdkLinkedList secondList = (JdkLinkedList) secondColl;
   int numNew = secondList.size();
   if (numNew == 0)  return false;
   modCount++;
   Entry<E> successor = (index == size ? header : entry(index));
   Entry<E> predecessor = successor.previous;
   // TODO LATER if reverse
   
   // connect the last element of this list with the first element of the second list
   // linked list is implemented as a 'cycle' => header.next == first element of second list
   Entry<E> first = secondList.header.next;
   predecessor.next = first;
   first.previous = predecessor;
   
   // append the last element of the second list with the rest of this list
   Entry<E> last = secondList.header;
   successor.previous = last;
   last.next = successor;
   

Answer 4

我认为用任何一种基本列表结构来编写这并不是太难，因为在中间链表中插入或链表中的末尾是O（1）。p>

Answer 5

FastList from javolution不是现成的解决方案，但tail（）和head（）非常接近我最喜欢的

我认为trove是解决方案，尽管在O（1）中没有方便的反转或addAll方法

Answer 6

如果您愿意满足于Iterable结果，您可以使用google collections Iterables。concat和Iterables。逆转

http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/Iterables.html

public static <T> Iterable<T> concat(Iterable<? extends T> a,
                                 Iterable<? extends T> b)

public static <T> Iterable<T> concat(Iterable<? extends T> a,
                                 Iterable<? extends T> b,
                                 Iterable<? extends T> c)

public static <T> Iterable<T> concat(Iterable<? extends T> a,
                                 Iterable<? extends T> b,
                                 Iterable<? extends T> c,
                                 Iterable<? extends T> d)

public static <T> Iterable<T> concat(Iterable<? extends T>... inputs)

public static <T> Iterable<T> concat(Iterable<? extends Iterable<? extends T>> inputs)