How is an ArrayList data structure indexed and dynamic at the same time? How is it implemented?

Question

I believe there is a difference between LinkedLists and ArrayLists. ArrayLists are nothing but dynamic arrays. So I assume ArrayLists are stored in the heap in contiguous locations (Thats the reason they have an O(1) get method). The question is, what if it happens that there is another object that was stored in the heap that would prevent the ArrayList from growing? How is it implemented in this case? If the remaining of the ArrayList is stored in other non-conrigous area of the heap, the get method wont be an O(1).

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

Answer 1

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