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

a->b->c->e->f->g
a->b->c->g->f->e
c->b->a->e->f->g
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:

is it possible with other collection libs?
how to concat the inverse?

Maybe duplicate. See this: http://stackoverflow.com/questions/2237308/merge-two-lists-in-constant-time-in-java — MicSim, Mar 22 '10 at 16:49
Can you describe an algorithm in a language neutral way that concatenates contents of linked lists in O(1)? — David Soroko, Mar 22 '10 at 16:49
@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. — Pops, Mar 22 '10 at 16:51
@David: language-independent, but java-like algorithm: `firstList.getLastElement().setNextElement(secondList.getFirstElement())` — Roman, Mar 22 '10 at 16:55
@David, It could be easily made O(1) if you kept a head/tail pointer with the nodes, granted it increases storage space, but that may not be a concern. — M. Jessup, Mar 22 '10 at 17:14
Thanks MicSim for the duplicate detection! I searched a lot but couldn't found this one. Now the question is if this is possible with other collection libs + concating the inverse — rocker, Mar 22 '10 at 17:17
for reference, the internals of LinkedList look something like http://developer.classpath.org/doc/java/util/LinkedList-source.html - perhaps just tweak some of the contents of that and roll your own. — Carl, Mar 22 '10 at 18:50
@Carl yes, see one of my answers. It is strange that event the classpath impl does not handle this specific usecase (although they aren't allowed to look into sun's sourcecode :-)) — rocker, Mar 24 '10 at 08:52

score 6 · Answer 1 · edited Apr 21 '13 at 19:03

6

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)

edited Apr 21 '13 at 19:03

Adrian Panasiuk

7,249
5
33
54

answered Mar 22 '10 at 17:52

Yardena

2,837
20
17

I'd say look at the code - I suspect that it will perform less well than addAll will. – TofuBeer Mar 22 '10 at 18:59
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. – Yardena Mar 22 '10 at 20:10
2

With the Iterables methods, you won't copy the list elements, resulting in less memory usage and probably a speed improvement compared to addAll. – Jared Levy Mar 28 '10 at 01:33
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. ;-) – trevore Sep 29 '15 at 09:48

score 2 · Answer 2 · answered Mar 22 '10 at 16:49

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.

answered Mar 22 '10 at 16:49

Roman

64,384
92
238
332

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() – rocker Mar 22 '10 at 17:21
3

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()); }` – Andrea Zilio Mar 22 '10 at 17:34

score 0 · Answer 3 · answered Mar 22 '10 at 16:58

0

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

answered Mar 22 '10 at 16:58

Jason M

512
2
8

4

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. – Joachim Sauer Mar 22 '10 at 17:02
Good point, I failed to dig deep enough into the Java specific objects. – Jason M Mar 22 '10 at 19:08

score 0 · Answer 4 · answered Mar 22 '10 at 18:49

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

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

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;

score 0 · Answer 5 · answered Mar 22 '10 at 18:58

0

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.

answered Mar 22 '10 at 18:58

TofuBeer

60,850
18
118
163

I'm sure in my usecase the concat of a linkedlist will be faster then the system.copy of arraylist – rocker Mar 22 '10 at 20:47
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. – TofuBeer Mar 22 '10 at 23:23
of course I will test the difference! But the question was about a fast concat method not about overall performance. – rocker Mar 24 '10 at 08:50
but a fast concat may be pointless in terms of performance, which might explain why one doers not exist. – TofuBeer Mar 24 '10 at 17:03

score 0 · Answer 6 · answered Mar 22 '10 at 20:45

0

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

answered Mar 22 '10 at 20:45

rocker

283
3
8

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

6 Answers6

Linked