collections - Is there a fast concat method for linked list in Java?

Question

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).

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

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.

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. is it possible with other collection libs?
2. how to concat the inverse?

Answer 1

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)