Difference between Array and ArrayList<> in Java in terms of memory allocation?

Question

I came accross an article which had a question-

Contiguous memory locations are usually used for storing actual values in an array but not in ArrayList. Explain.

https://www.geeksforgeeks.org/java-interview-questions/#:~:text=Contiguous%20memory%20locations%20are%20usually%20used%20for%20storing%20actual%20values%20in%20an%20array%20but%20not%20in%20ArrayList.%20Explain.

Following lines in the above post creates some confusion-

The elements of an array are stored in contiguous memory locations, which means that each element is stored in a separate block based on it located within the array. Since the elements of the array are stored in contiguous locations, it can be relatively easy to access any element by its index, as the element address can be calculated based on the location of the element. But Java implements ArrayLists as dynamic arrays, which means that the size can change as elements are removed or added. ArrayList elements are not stored in contiguous memory locations in order to accommodate this dynamic nature.

           public static void main(String[] args) {
                    int primitiveArray[]=new int[5];
                    Integer objectArray[]=new Integer[5];
                    ArrayList<Integer> list=new ArrayList<>(5);
                    for(int i=0;i<5;i++){
                      primitiveArray[i]=i;
                      objectArray[i]=i;
                      list.add(i);
                    }

           }        

Now, what I understand is when I create the primitive array, the elements are stored in continuous memory locations. When I create an Integer array, the objects are created on the heap (may not be in continuous memory locations) and there references are stored in continuous memory locations. When I create an ArrayList, it uses an Object[] array internally and stores the references of the objects (created on heap which may not be continuous) in continuous memory locations.
So, what is right? The text which I quoted from the article or the explanation which I gave (which I found here- https://www.geeksforgeeks.org/internal-working-of-arraylist-in-java/)? Please help me understand the concept!

Answer 1

Your understanding is correct (as far as I can tell).

So I will focus on the text you quoted from the Geeks For Geeks Interview Questions page:

The elements of an array are stored in contiguous memory locations,

This is correct, but incomplete. For an array of primitive types the primitive values are stored in contiguous locations. But for an array of a reference type, it is the element references that are stored in contiguous memory locations.

... which means that each element is stored in a separate block based on it located within the array.

This an incorrect (or garbled) definition of contiguous locations. (It is not even grammatical English!) What contiguous locations actually means is that the locations are one after another memory ... with no gaps. So for example, in a byte[], the bytes will be stored in memory with no gaps in between them, and likewise for other primitive arrays and for object arrays.

In other words, this is the normal meaning of the English word "contiguous".

Since the elements of the array are stored in contiguous locations, it can be relatively easy to access any element by its index, as the element address can be calculated based on the location of the element.

This sentence is correct. But it applies to ArrayLists too!

But Java implements ArrayLists as dynamic arrays, which means that the size can change as elements are removed or added.

This is misleading. An ArrayList is a List, and lists typically behave rather like¹ dynamic arrays. But an ArrayList is implemented with a backing array that is a genuine Java object array. And that array is fixed sized ... like all Java arrays. The "trick" is that the ArrayList implementation will create a new backing array if it finds that the existing one is too small when an element is added to the list.

ArrayList elements are not stored in contiguous memory locations in order to accommodate this dynamic nature.

This is not correct.

In fact ArrayList elements >are< held in contiguous memory in the same sense that object array elements are contiguous (see above!). The element references are held in contiguous memory locations in the backing array, but they will refer to objects held in the heap. Those objects will nearly always be in non-contiguous memory locations.

The "dynamic nature" is accommodated by allocating a new backing array and copying elements. (You can check the source code of ArrayList to see how it is done.)

---

^{1 - But not completely. For instance, the List API doesn't provide a way to directly increase the size of the list by N elements, as you would expect for a true dynamic array API.}

Answer 2

Your understanding is right. When storing primitive types in a Java array, they are saved in contiguous memory allocation. Each element directly holds the value of the primitive type, such as an integer, floating-point number, or boolean.

On the other hand, when creating an array of objects or Integers, it is essentially an array of references. These references are also stored in contiguous memory allocation, meaning they are placed one after another in memory. However, the references themselves point to different locations in memory where the actual objects or Integer values are stored.

For example, consider an array of Objects. Each element in the array is a reference to an Object stored elsewhere in memory. The references themselves are stored sequentially in the array, but they can point to objects scattered throughout the memory.

The ArrayList implementation stores items in the Object[] elementData, which means the items are not saved in contiguous memory allocation.

Check the source code for more info https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/ArrayList.java

/**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access

/**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     * @throws OutOfMemoryError if minCapacity is less than zero
     */
    private Object[] grow(int minCapacity) {
        int oldCapacity = elementData.length;
        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            int newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity, /* minimum growth */
                    oldCapacity >> 1           /* preferred growth */);
            return elementData = Arrays.copyOf(elementData, newCapacity);
        } else {
            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
        }
    }

Answer 3

Yes, even if you create a primitive array, the array will be stored in the heap only with a continuous memory allocation.

In Java, objects are created on the heap only. So whenever you use the new operator you can be sure that the object will be stored on the heap. For example, int primitiveArray[] = new int[5];

Now the question is that ArrayList uses a continuous memory allocation or not. According to me, ArrayList also has a continuous memory allocation because the underling implementation of ArrayList is the array itself and an array uses continuous memory allocation.

As per Java documentation:

The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.

When you use ArrayList then references of the objects will be stored in continuous memory allocation, but the references may not be continuous.

As you have already stated, this in your question:

When I create an ArrayList, it uses an Object[] array internally and stores the references of the objects (created on heap which may not be continuous) in continuous memory locations.

This is correct.

Answer 4

"I came accross an article which had a question ...

... Following lines in the above post creates some confusion ..."

The data within the primitive array will be stored contiguously, as its content is a sequence of literal values.
Whereas, the Object array size would require a computation.

Consider the following examples.

This can be calculated, since the data is static; 3, 32-bit values.

int[] values = { 1, 2, 3 };

Whereas, this will only be contiguous initially.  Since an adjustment of value, after the initialization, will re-order the object within the heap.

void example() {
    Example[] values = new Example[3];
}

class Example {
    int value;

    void setValue(int value) {
        this.value = value;
    }
}

"... Now, what I understand is when I create the primitive array, the elements are stored in continuous memory locations. ..."

Correct; contiguous, it means sequential.

"... When I create an Integer array, the objects are created on the heap (may not be in continuous memory locations) and their references are stored in continuous memory locations. ..."

So, the heap doesn't have any type of contiguous memory, it's just an allocation and a look-up table used by the JVM.
The objects will move to different locations within the heap as the data evolves.

The stack, on the other hand, is a queue, so every element is contiguous, by default.

"... When I create an ArrayList, it uses an Object[] array internally and stores the references of the objects (created on heap which may not be continuous) in continuous memory locations. ..."

No.  The addresses of the objects, within the ArrayList may appear anywhere within the heap, so they won't, reliably, be contiguous.

For example, say you create an ArrayList and add 3 objects to it.
You can presume they are most likely one after the other, in the heap—so, here they are contiguous by default.

Now, imagine your code continues and allocates various heap memory for other miscellaneous objects.

You then add 3 more objects to the ArrayList.
These 3 new objects will not be appended to the initial 3 objects within the ArrayList, they will simply be placed in the heap, and added to the JVM's look-up table.

"... So, what is right? ... Please help me understand the concept!"

I recommend researching the differences of the stack and heap memory allocations.
The concept you are considering has to do with these two types of storage principles.