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

collections java linked-list apache-commons guava

2022-09-02 04:48:11

我怎样才能通过jdk1.6，谷歌或apache共享资源集合或其他方式将O（1）中的两个链接列表与Java连接起来？例如，在jdk中，只有addAll方法，即O（n）。

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

a->b->c->e->f->g
a->b->c->g->f->e
c->b->a->e->f->g
c->b->a->g->f->e

您是否知道这样的列表实施，或者我必须实现自己的链表？了解如何调整现有解决方案也会有所帮助（例如，jdk LinkedList只有很多私有方法）。这些功能在我看来非常明显，希望我没有错过一些愚蠢的东西。

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

是否可以使用其他集合库？
如何连接逆向？

答案 1

如果你愿意满足于迭代的结果，你可以使用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)

答案 2

我目前看到的唯一解决方案是实现List，制作一个构造函数，如：

public EnhancedList (List l1, List l2)

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