Is there a fast concat method for linked list in Java?
How can I concat two linked lists in O(1) with Java via jdk1.6, google or apache commons collection or whatever? Eg in the jdk there is only the addAll method which is O(n).
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
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 (eg the jdk LinkedList has a lot of private methods only). These features seems to me very obvious, hopefully I am not missing something stupid.
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:
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)
The only solution I see at the moment is to implement List, make a constructor like:
public EnhancedList (List l1, List l2)
and override all methods. In such solution it's actually not important whether you want to concat LinkedLists or any other lists.
我认为用任何类型的基本列表结构编写都不会太困难，因为在链接列表的中间或列表末尾插入O（1）。
链接地址: http://www.djcxy.com/p/3362.html