Which Java collection allows cheap appending?

Question

I am searching for a list data structure in Java which allows cheap appending of long lists. I tried LinkedList but I found in the documentation of addAll, that an iterator is used to append the two lists. This means that the list, which gets appended, gets cloned during the operation. The iterator walks though the whole list returning every single element. Is there any collection available which omits the iteration while appending two lists?

Answer 1

You can use Guava's Iterables.concat method to create concatenated Iterable View..

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

• This does not copy elements from one list to another..
• So, it does not change any of your lists..
• Also, this does not create a new list (It creates an Iterable which is not a list)

Basically it creates an Iterable through which you can iterate over the two lists back to back (It iterates elements from list1 then from list2..

NOTE: - If you want a list as a concatenation of the two lists, then this might not help you much.. Because, it does not create a list, but an Iterable.. For that case, you have no other choice than Iterating over your lists and copy each of your reference..

From the docs: -

It Combines two iterables into a single iterable. The returned iterable has an iterator that traverses the elements in a, followed by the elements in b. The source iterators are not polled until necessary. The returned iterable's iterator supports remove() when the corresponding input iterator supports it.

You also have a var-args version of this method.. See Docs.. This can take any number of lists, and returns Iterables that can iterate over those lists in order.. So, you can do like this..

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

This link --> google-guava-libraries-essentials might also be of interest to you..

Answer 2

Not really, since all "append" operations don't make any assumptions about the underlying collections. Technically two linked lists could be appended directly, but the append has to be generic so it uses iteration.

Another good reason to not allow direct concatenation is the fact that after the append changing one list will also affect the other, which I'm sure is not a desirable property.

Answer 3

addAll in ArrayList converts it to an Array and then uses a system call to copy (System.arraycopy). This should be quicker than looping through in java as it is native, I dont think there is a cheap appender.

Answer 4

May be addAll of ArrayList should be quicker because it doesn't iterate , but use System.arrayCopy.The code looks like

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
        int numNew = a.length;
    ensureCapacity(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
    return numNew != 0;
    }

Answer 5

This means that the list, which gets appended, gets cloned during the operation.

Creating an iterator doesn't clone the collection.

The addAll method in most cases calls toArray() to ensure the data is extracted atomically which clones the elements of the collection as an array and this is likely to use an Iterator to do it.

Is there any collection available which omits the iteration while appending two lists?

No, but you can iterate the collection yourself if this is really important.

---

The most efficient is likely to be

List<E> list1 = ... random access list ...
List<E> list2 = ... random access list ...

for(int i = 0; i < list2.size(); i++)
    list1.add(list2.get(i));

This doesn't create any objects and has O(n) time where n is the size of list2.

Answer 6

Even if you do find such a collection class you couldn't be guaranteed that it will continue to work that way in future versions of Java. That's because this is a behavior that's not specified in the Collection interface and is therefore subject to the whim of the class developer.

You could, of course, write your own collection class, but even then you'd be making assumptions about the behavior of other Collection classes

Answer 7

Default implementation of addAll method in AbstractCollections uses iterator to add but addAll method is overridden in sub classes which provides custom specific implementation

Like

• ArrayList uses System.arraycopy
• LinkedList uses a Loop to traverse through elements.

Answer 8

I think there is no way with the standard API, but depending on your needs you would try to implement one by yourself. For example, you can implement one which internally has a List of collection references, added every time you call the addAll method.

Answer 9

with that behavior the list added to the first list will get consumed (i.e. modified) or results in the second list becoming a sublist of the bigger one with all kinds of gotchas (like what happens if you add a list twice...),

the addAll has an implicit const argument (meaning that the second list will remain unmodified over several calls), so this behavior won't exist unless you roll your own

Answer 10

I would simply take ArrayList, and happily addAll() my stuff to it. It doesn't really matter how the chosen List implementation performs the addAll() operation, iteration or toArray are both relatively cheap and its very unlikely this will be a performance bottleneck (that assuming your application does useful work with the list elements and not just create lists...).

There is really no way around the iteration in addAll(), if you want an independent list that contains the elements from N source lists, the element references have to be copied somewhere (you could change the source lists after addAll(), but that must not affect the conactinated list, thus a copy is unavoidable).

If you do not really need the List semantics (independend of the sources), then make use of the already suggested Guava to create a view of multiple lists (or roll your own, its not rocket science if you don't want the dependency).