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.
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!
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 like1 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.