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?

• MicSim: Maybe duplicate. See this: stackoverflow.com/questions/2237308/…
• David Soroko: Can you describe an algorithm in a language neutral way that concatenates contents of linked lists in O(1)?
• Pops: @rocker: Welcome to SO. For future reference, just because of the way SO is structured, it's better to ask about even related topics (in your case, concat and inverse) as separate questions. People like to be able to focus on one of the topics at a time.
• Roman: @David: language-independent, but java-like algorithm: firstList.getLastElement().setNextElement(secondList.getFirstElement())
• David Soroko: @Roman this is O(N) where N is the size of secondList.

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)

• TofuBeer: I'd say look at the code - I suspect that it will perform less well than addAll will.
• Yardena: The methods create a new object that delegates to the original list(s). It's always good to check performance/memory impact, as it depends on the usage.
• Jared Levy: With the Iterables methods, you won't copy the list elements, resulting in less memory usage and probably a speed improvement compared to addAll.
• trevore: Using ArrayList I have noticed that it is much faster to simply use addAll and generate a new list when iterator is often accessed. This was happening so often in our code, we had a performance increase of up to 50 % when using addAll. ;-)

Answer 2

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.

• rocker: I actually though there would be an out-of-the-box solution. If I had to roll out my own I would do it via MyLinkedList.addAll(Collection) -> detect LinkedLists and to create the inverse: MyLinkedList.inverse()
• Andrea Zilio: I was just proposing the same solution (so +1 ;)). I think that what Roman is proposing is to implement a List interface such that you can use this implementation as a single list while its methods works on both the single lists from which it has been created. For example the new get method will return an element from the first list or the second list: public T get(int i) { return i < list1.size() ? list1.get(i) ? list2.get(i - list1.size()); }

Answer 3

I'd think this wouldn't be too difficult to write with any kind of base list construct since insertion in the middle or the end of a list in a Linked list is O(1).

• Joachim Sauer: The problem is that a LinkedList is a stand-alone object in Java and doing that operation while also keeping both LinkedList objects intact and standalone is not a O(1) operation, as you'll have to copy one list.
• Jason M: Good point, I failed to dig deep enough into the Java specific objects.

Answer 4

Adapting the LinkedList to get O(1) concat in the jdk will work if:

1. the method entry() and the variables header and size and the inner class Entry would be protected

2. addAll would detect LinkedList and then doing sth. like:

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

Answer 5

For the concat I would suggest you do the following:

• Make sure all of your parameters/variables are declared as List<...> not LinkedList<...>
• Change the new LinkedList<...>(); to new ArrayList<...>();
• profile the application
• Change the new ArrayList<...> to new LinkedList<...>();
• profile the application

Depending on your usage ArrayList can be significantly faster than LinkedList. Also looking at the profile data you can see how much of a performance hit you have by using addAll - if it isn't that large don't bother "fixing" it.

For some things your experiences with other languages will not hold true. You may find that addAll meets your requirements in Java.

If you were to write your own concatable list make sure it conforms to the List interface then change your code and re-profile it and make sure it is faster. If it isn't then throw it away and stick with the standard List types.

• rocker: I'm sure in my usecase the concat of a linkedlist will be faster then the system.copy of arraylist
• TofuBeer: More to that... if you are iterating over the list a lot, for example, the cost of iterating over the linkedlist will be more than the cost of iterating over the arraylist. As such the time spent in the addAll may cancel out the time sent iterating. There are other things like that that could make the overall performance of ArrayList faster than a LinkedList. But really, never assume when it comes to performance - always measure.
• rocker: of course I will test the difference! But the question was about a fast concat method not about overall performance.
• TofuBeer: but a fast concat may be pointless in terms of performance, which might explain why one doers not exist.

Answer 6

FastList from javolution is not an out-of-the-box solution but with the tail() and head() quite close to my favourite.

I think trove is the solution, although no convenient method exist for invert or addAll in O(1).