Java 中的链表是否有快速的 concat 方法? [英] Is there a fast concat method for linked list in Java?

问题描述

如何通过 jdk1.6、google 或 apache commons 集合或其他方式将 O(1) 中的两个链表与 Java 连接起来?例如.在 jdk 中只有 O(n) 的 addAll 方法.

How can I concat two linked lists in O(1) with Java via jdk1.6, google or apache commons collection or whatever? E.g. in the jdk there is only the addAll method which is O(n).

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

Another feature I miss is to concat two lists where each of them could be in inverse order. To illustrate this assume two lists a->b->c and e->f->g could merged into

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 只有很多私有方法).这些功能在我看来非常明显，希望我没有遗漏一些愚蠢的东西.

Do you know of such a list implemenation or do I have to implement my own linked list? It would be also helpful to know how to tweak existing solutions (e.g. the jdk LinkedList has a lot of private methods only). These features seems to me very obvious, hopefully I am not missing something stupid.

正如 MicSim 指出的问题 在 Java 中以恒定时间合并两个列表 是相关的，但不是真正的重复！现在的问题是:

As MicSim pointed out the question Merge two lists in constant time in Java is related but not a real duplicate! Now the questions are:

1. 是否可以使用其他集合库?
2. 如何连接逆序?

推荐答案

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

If you are willing to settle for Iterable result, you can use google-collections Iterables.concat and 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)

这篇关于Java 中的链表是否有快速的 concat 方法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！