How is an ArrayList data structure indexed dynamically at the same time? How is this implemented?

Question

I believe that there is a difference between LinkedLists and ArrayLists. ArrayLists are nothing more than dynamic arrays. Therefore, I assume that ArrayLists are stored on the heap in contiguous places (thats the reason they have the O (1) get method). The question is, what if there is another object that has been stored on the heap that will prevent the growth of the ArrayList? How is this implemented in this case? If the remaining ArrayList is stored in another substandard area of ​​the heap, the get method will not be O (1).

For example, suppose there is an object 10 in the memory location. After that, an ArrayList is created in memory location 5. For simplicity, we assume that each element in the array list is just one byte. This means that an ArrayList can grow up to 5 elements.

Answer 1

ArrayList can grow to any size, limited by available memory, discarding its old array, allocating a completely new one and copying the values ​​from the old array to the new one. This operation can take O(n) for any given insert, the amortized cost of O(1) .

Answer 2

So, I assume that ArrayLists are stored on a heap in contiguous places

This is usually the case, but nothing prevents the JVM from doing something else (nothing in the JVM specs says the array should be stored in contiguous blocks).

See also this related post .

What if there is another object that was stored on the heap that will prevent the growth of the ArrayList?

The arraylist object will ask the JVM to provide it with more space that the JVM will allocate at will (or throw an OutOfMemoryException if it cannot).

Answer 3

Based on the source code (thanks @GilbertoGaxiola), the source ArrayList creates an object [] of size 10. Since it needs more space, it doubles the size and copies the contents of the old array to the new array. It does not take many times before this array is huge, which makes it a great implementation.

Answer 4

So, I assume that ArrayLists are stored on the heap in contiguous places (thats the reason they have the O (1) get method).

All other answers here are correct, but I want to turn to the incorrect assumption that you made here:

ArrayList.get() is O (1) not because of how the array is stored in memory, but because the cost of accessing an element is constant and not proportional to the number of elements in ArrayList.

O (1) here does not mean that the search can be performed in one operation - this means that the complexity is constant in relation to the size of the support array.

When you call ArrayList.get(i) , the JVM still needs to translate the array index into a virtual memory address in which your OS translates the address into real, but it is O (1), because the complexity is the same, the array has 1 element or 5000.

For comparison, LinkedList.get(i) not O (1), because the LinkedList class must go through each node until it finds node i - the complexity is proportional to the total size of the list and the value of i .

The assumption that the array is stored in contiguous places is also incorrect.

Answer 5

The last explanation is absolutely true. Os must ultimately translate the index into a real address. Thus, the time spent on translation is constant for all indices. Regarding storage, the last explanation is true, the size just doubles if you need to save more items.