is memory contiguously allocated for arraylists?

Question

When we use new ArrayList() is memory contiguously allocated? If we call list.add(e) 10 times, will all elements be contiguously stored in memory by add order, or will they be randomly stored in memory?

Guaco

Why do you care? If you must know, read this: grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/… GrepCode is your friend for this type of question. – Trisomic

Well, ArrayList is based on Java arrays. And Java arrays are not guaranteed to be contiguous in memory. But why does it matter anyway. – Groundhog

I would have thought that the answer would be OS specific anyway – Narcotism

@JimGarrison Surely a thorough mental model is always a good thing? Or, simple curiosity? Knowing the answer can help to get a thorough grasp on, for instance, the differences between simple Arrays and ArrayLists in memory. – Crosson

Even if it memory was initially allocated continuously, the JVM may at any time change the actual memory address of anything and everything. Real memory addresses are irrelevant and fluid. – Astonishing

Answer 1

Firstly you need to understand how ArrayList works. It stores "references" or "pointers" to actual storage in an internal object array elementData. This array of references may well be contiguous, but is JVM specific. The actual objects being added are stored on the heap, and almost certainly won't be contiguous, although this is JVM specific.

elementData[0] ===> object 1
elementData[1] ===> object 2
elementData[2] ===> object 3
...

Secondary, you mention calling add() multiple times... When ArrayList internal elementData is no longer big enough it resizes it to a bigger one, +50% IIRC, and copies all the references to the new elementData, the actual objects do not move.

Lastly contiguous memory is typically a concern of high-performance native applications. In Java memory is managed by the JVM and is borrowed from the underlying OS, in turn from the hardware, or even virtualized hardware.

Underside

The reason I was just searching for this is because I was reading of advantages of various data structures over others, and one of the advantages of arrays is contiguous memory allocation. I am assuming ArrayLists do not have that advantage from your answer.. – Mraz

In terms of relative cost yes Arrays will be almost certainly be quicker in Java than say a linked list. However Java does make guarantees about how structures map onto underlying memory in the same way say C++ does – Underside