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

如何通过jdk1.6，google或apache commons集合或其他任何方式将O（1）中的两个链接列表与Java连接起来？ 例如，在jdk中，只有addAll方法是O（n）。

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

1. A-> B-> C-> E-> F->克
2. A-> B-> C-> G-> F->电子
3. C-> B-> A-> E-> F->克
4. C-> B-> A-> G-> F->电子

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

正如MicSim指出的那样， 在Java中使用Merge两个列表的常量时间是相关的，但不是真正的重复！ 现在的问题是：

1. 是否有可能与其他集合库？
2. 如何连续反转？

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  Iterable concat(Iterable a, Iterable b) public static  Iterable concat(Iterable a, Iterable b, Iterable c) public static  Iterable concat(Iterable a, Iterable b, Iterable c, Iterable d) public static  Iterable concat(Iterable... inputs) public static  Iterable concat(Iterable> inputs) 

Answer 2

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

 public EnhancedList (List l1, List l2) 

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

Answer 3

我认为使用任何类型的基本列表构造都不会太难写，因为在链表中的列表的中间或末尾插入是O（1）。

Answer 4

如果符合以下条件，调整LinkedList以在jdk中获得O（1）concat将起作用：

1. 方法entry（）和变量头和大小以及内部类Entry将受到保护

2. addAll会检测LinkedList然后做某事。 喜欢：

    JdkLinkedList secondList = (JdkLinkedList) secondColl; int numNew = secondList.size(); if (numNew == 0) return false; modCount++; Entry successor = (index == size ? header : entry(index)); Entry 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 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 last = secondList.header; successor.previous = last; last.next = successor; 

Answer 5

对于concat，我建议你做以下事情：

• 确保所有参数/变量都声明为List <...>而不是LinkedList <...>
• 更改新的LinkedList <...>（）; 到新的ArrayList <...>（）;
• 描述应用程序
• 将新的ArrayList <...>更改为new LinkedList <...>（）;
• 描述应用程序

根据您的使用情况，ArrayList可能比LinkedList快得多。 另外，通过查看配置文件数据，您可以看到使用addAll可以获得多少性能 – 如果不是那么大，则不会“修复”它。

对于某些事情，您使用其他语言的经验不会成立。 您可能会发现addAll满足您在Java中的要求。

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

Answer 6

来自javolution的FastList不是一个开箱即用的解决方案，但tail（）和head（）非常接近我最喜欢的。

我认为特洛伊是解决方案，尽管在O（1）中没有方便的方法用于反转或addAll。