Matthew
Matthew

Reputation: 191

Java ArrayList storage

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

Answers (2)

JNYRanger
JNYRanger

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

arshajii
arshajii

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

Related Questions