Java中是否有快速的链表连接方法？

Question

如何使用Java通过jdk1.6、Google或Apache Commons集合等方式以O(1)拼接两个链表？例如，在jdk中只有O(n)的addAll方法。

我错过的另一个功能是连接两个列表，其中每个列表都可以是反向的。为了说明这一点，假设有两个列表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只有很多私有方法）。这些特性对我来说似乎非常明显，希望我没有错过什么愚蠢的东西。

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

1. 是否可以使用其他集合库实现？ 2. 如何连接相反的列表？

- rocker

---

你能用一种语言中立的方式描述一个算法，以O(1)的时间复杂度连接链表的内容吗？ - David Soroko

@rocker：欢迎来到SO。以后参考一下，由于SO的结构，最好将相关主题（在您的情况下是concat和inverse）作为单独的问题提出。人们喜欢能够一次专注于一个主题。 - Pops

@David：与语言无关，但类似于Java的算法：firstList.getLastElement().setNextElement(secondList.getFirstElement())。 - Roman

@Roman 这是 O(N) 的算法，其中 N 是 secondList 的大小。 - David Soroko

请参考LinkedList的内部结构，该链接如下：http://developer.classpath.org/doc/java/util/LinkedList-source.html。或许只需要微调其内容并自行实现。 - Carl

Answer 1

如果您愿意接受Iterable结果，可以使用google-collections库的Iterables.concat和Iterables.reverse。

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)

- Yardena

---

我会建议看一下代码 - 我怀疑它的性能不如addAll。 - TofuBeer

这些方法创建一个新对象，该对象委托给原始列表。检查性能/内存影响总是很好的做法，因为它取决于使用情况。 - Yardena

使用可迭代方法，您不会复制列表元素，从而减少内存使用量，并且与addAll相比可能会有速度改善。 - Jared Levy

使用ArrayList时，我注意到当迭代器经常被访问时，简单地使用addAll并生成一个新列表会更快。在我们的代码中，这种情况发生得如此频繁，因此使用addAll时性能提高了多达50％。;-) - trevore

Answer 2

我目前唯一能想到的解决方法是实现一个List，创建如下构造函数：

public EnhancedList (List l1, List l2)

覆盖所有方法。在这种解决方案中，你想要连接LinkedLists或任何其他列表都不重要。

- Roman

---

我本来以为会有现成的解决方案。如果我不得不自己实现，我会通过 MyLinkedList.addAll(Collection) -> 检测 LinkedList 并创建反向链表：MyLinkedList.inverse()。 - rocker

我只是提议相同的解决方案（所以+1 ;）。 我认为Roman提出的建议是实现一个列表接口，使您可以将此实现用作单个列表，而其方法会对创建它的两个单个列表同时起作用。 例如，新的get方法将从第一个列表或第二个列表返回元素：public T get(int i) { return i < list1.size() ? list1.get(i) ? list2.get(i - list1.size()); } - Andrea Zilio

Answer 3

如果将LinkedList适应到JDK中以获得O(1)的连接，需要满足以下条件：

1. 方法entry()和变量header、size以及内部类Entry将被保护。

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
   
   // 将此列表的最后一个元素与第二个列表的第一个元素连接起来
   // 链表被实现为“循环” => header.next == 第二个列表的第一个元素
   Entry<E> first = secondList.header.next;
   predecessor.next = first;
   first.previous = predecessor;
   
   // 将第二个列表的最后一个元素附加到此列表的其余部分
   Entry<E> last = secondList.header;
   successor.previous = last;
   last.next = successor;
   

- rocker

Answer 4

我认为使用任何类型的基本列表结构编写这个程序都不会太困难，因为在链表中插入元素到中间或末尾的时间复杂度是O(1)。

- Jason M

---

问题在于，在Java中，LinkedList是一个独立的对象，而要同时保持两个LinkedList对象的完整性和独立性进行该操作不是O(1)操作，因为你需要复制一个列表。 - Joachim Sauer

好的观点，我没有深入挖掘Java特定的对象。 - Jason M

Answer 5

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

• 确保所有参数/变量都声明为List<...>而不是LinkedList<...>
• 将new LinkedList<...>();更改为new ArrayList<...>();
• 分析应用程序
• 将new ArrayList<...>更改为new LinkedList<...>();
• 分析应用程序

根据您的使用情况，ArrayList可能比LinkedList快得多。此外，查看配置文件数据时，您可以看到使用addAll会带来多大的性能损失-如果不是很大，请不要费心“修复”它。

对于某些事情，您在其他语言中的经验可能不适用。您可能会发现，在Java中，addAll符合您的要求。

如果您要编写自己的可连接列表，请确保它符合List接口，然后更改代码并重新分析它，以确保它更快。如果不是，则将其丢弃并坚持使用标准列表类型。

- TofuBeer

---

我相信在我的使用情况下，链表的连接速度将比ArrayList的系统复制更快。 - rocker

更进一步地说，如果您经常迭代列表，例如，迭代LinkedList的成本将比迭代ArrayList的成本更高。因此，在addAll中花费的时间可能会抵消迭代的时间。还有其他类似的事情，这可能使ArrayList的整体性能比LinkedList更快。但是，真正重要的是，在涉及性能时永远不要做出假设-始终进行测量。 - TofuBeer

当然我会测试它们的差异！但问题是关于快速连接方法而不是整体性能。 - rocker

但是在性能方面，快速的连接可能是毫无意义的，这也许可以解释为什么它不存在。 - TofuBeer

Answer 6

javolution的FastList并不是一个开箱即用的解决方案，但通过tail()和head()方法已经非常接近我最喜欢的了。

我认为trove才是解决方案，尽管没有O(1)的便捷方法来进行invert或addAll操作。

- rocker