Reputation: 191
I know that ArrayLists references are stored contiguously in the heap. However, if I add in an element into the middle of an array list
ArrayList<Double> list = new ArrayList<Double>(Collections.nCopies(10, 6.5));
list.add(5, 20.0);
How does this change the way it is stored in the heap? Is the location of the first reference moved to a new memory cell or is everything just moved past the memory cell 5 moved down after 20.0 is inserted?
Upvotes: 3
Views: 1739
Reputation: 7097
When you create a Collection object it allocates a certain size internal array. This is usually larger than one if initializing an empty ArrayList. When you hit a maximum capacity limit, the collection will automatically create a new internal array larger than the current one and copies the elements to the new one. In many implementations whenever you hit the 'limit' of the array it doubles in size.
In this particular case you are creating an underlying array with the size of 10, and then it performs the expand & copy operation during the processing of the called add method.
Upvotes: 1
Reputation: 129557
It depends.
Think of an ArrayList
as (internally) a fixed-size buffer that is resized whenever it runs out of space. If you try to insert an element in the middle, and there is space left in the buffer, then everything can simply be shifted down to make room for the new element. But, if there is no space left, then the buffer needs to be resized, which entails reallocating it, which in turn could entail copying all of the elements to a new location in memory. Note that the decision to move the buffer to a new location is not made by the Java Virtual Machine, but rather by the operating system.
Upvotes: 2