Justin A Justin A - 2 months ago 14
Java Question

Java 8 ArrayList. Which is it faster? Insert one item at index 0 or create new List with one item and addAll to the new List?

Lets assume I call a third party API and get back a mutable N-many list of objects. This list could be as small as 10 objects or as large as a few thousand. I then always want to insert just one object at index 0 of that returned List. I know i can easily call add at index 0 but this is going to be O(n) as it shifts every object for the insert. My question is, would it be faster on average (processing wise) to create a new List with the item i plan on inserting at the beginning and then call addAll on that new List passing in the returned 3rd party N-many List?

Answer

It depends on the list implementation. If you truly have no visibility of what list implementation your third-party has given you, all you can do is empirical testing and benchmarking.

More likely, they're returning you one of the standard Java list types, and indeed you've tagged your question arraylist -- is that what you're given?

ArrayList.add(index,element) uses System.arrayCopy() to copy each shifted element from index n to n+1, then writes the new element to its slot. That's O(n), however it's likely to be very fast indeed, since it will use the highly optimised system memmove routine to move whole chunks of RAM at a time. (see Why is memcpy() and memmove() faster than pointer increments? ).

In addition, if your extra element nudges the size of the list past the size of the allocated backing array, Java will create a new array and arraycopy the whole lot into there.

Bear in mind that you're only copying object references, not whole objects, so for 1000 elements, you're copying (worst case on a 64 bit machine) 64 bits * 1000 == 8 kilobytes of RAM.

Still, for really huge lists, the time it takes might become significant. Inserting into a linked list is cheaper (should be O(1) at the start or end)

You can make it an O(1) operation on an arbitrary List implementation by writing/finding a List implementation that is just a wrapper around the existing list. For example:

public class HeadedList implements List {

    private final List tail;

    public HeadedList(T head, List tail) {
       this.head = head;
       this.tail = tail;
    }

    public T get(int index) {
        return index == 0 ? head : tail.get(index - 1);
    }

    ...
}

(NB if you work in languages like Lisp/Clojure/etc you get very used to thinking of lists in this way)

But, only bother with this if benchmarking reveals that real performance problems are being caused by list building.

Comments