algorithm - Java merge 2 collections in O(1)

Question

I need to be able to merge 2 large collections into 1. Which collection type can I use best? I don't need random access to the individual elements. Usually I'd go for a linkedlist, however I can't merge 2 linkedlist in Java with a runtime of O(1), which could be done in many other languages, since I'll have to copy each element to the new list.

Edit: Thank you for all your answers. Your answers were all very helpful, and I managed to get the job done. Next time I will use my own implementation of a linked list to begin with.

question from:https://stackoverflow.com/questions/8368111/java-merge-2-collections-in-o1

Answer 1

You can create a concatenated Iterable view in O(1) using one of Guava's Iterables.concat methods:

Iterable<T> combined = Iterables.concat(list1, list2);

This will allow you to iterate over all the elements of both lists as one object without copying any elements.