What is the runtime of operations on Java's Arraylist?

Question

It seems like there is no official benchmarks for some of the very commonly used classes, for example ArrayList.

I could not find the documentation on the runtime for insert or remove. Compared to Python's List, which is similar to ArrayList, there is a well documented runtime complexity (see link above).

This post, gave some somewhat detailed benchmark on removing and copying elements from an ArrayList, but it still doesn't give the exact complexity analysis. I'm working on a project which takes extremely long data (~500,000 data points) so I can't sit back and assume removing or inserting data from ArrayList operates in constant time like magic. Where can I find this information?

Why don't you start by reading about how `List` implementations work in java. Then run your own benchmarks with your use cases. — Boris the Spider, Mar 29 '13 at 23:06
Straight from the javadoc: *The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.* — JB Nizet, Mar 29 '13 at 23:24
Or this cheat sheet http://www.coderfriendly.com/wp-content/uploads/2009/05/java_collections_v2.pdf and this SO question http://stackoverflow.com/questions/559839/big-o-summary-for-java-collections-framework-implementations — andersoj, Mar 30 '13 at 02:20

Kirby · Accepted Answer · 2013-03-29T23:21:47.260

For some quick references of Java complexities:

But really, nothing beats looking to the source, which can be found here.

Regarding the particular question of adding to an ArrayList, for example, we can see:

public boolean add(E e) {
           ensureCapacityInternal(size + 1);  // Increments modCount!!
           elementData[size++] = e;
           return true;
       }

The complexity for this operation clearly depends on ensureCapacityInternal:

private void ensureCapacityInternal(int minCapacity) {
               modCount++;
               // overflow-conscious code
               if (minCapacity - elementData.length > 0)
                   grow(minCapacity);
           }

Which depends on grow:

private void grow(int minCapacity) {
           // overflow-conscious code
           int oldCapacity = elementData.length;
           int newCapacity = oldCapacity + (oldCapacity >> 1);
           if (newCapacity - minCapacity < 0)
               newCapacity = minCapacity;
           if (newCapacity - MAX_ARRAY_SIZE > 0)
               newCapacity = hugeCapacity(minCapacity);
           // minCapacity is usually close to size, so this is a win:
           elementData = Arrays.copyOf(elementData, newCapacity);
       }

So we can see that the grow operation happens conditionally, and that in many cases, adding will be an O(1) operation. But you can also see from this the details of when the array will grow.

That's not very helpful - it doesn't cover the complexities of collection complexity. For example that a `LinkedList` never has to expand to so `add` always takes the same constant time whereas for an `ArrayList` there sometimes needs to be a `System.arraycopy` call. — Boris the Spider, Mar 29 '13 at 23:11
Yes, like I said, it's good to have an understanding of how the collection implementation works. Still, I feel that such a reference is helpful, because it is somewhat analogous to the example list the OP provided for Python list. — Kirby, Mar 29 '13 at 23:13
To allow for understanding of what actually happens for the different ArrayList operations, I've provided a link to ArrayList source. — Kirby, Mar 29 '13 at 23:16
Which source is that? i remeber an different ArrayList implementation, especilly in grow i remember a System.arraycopy. — AlexWien, Mar 30 '13 at 02:11

What is the runtime of operations on Java's Arraylist?

1 Answers1