Does inserting into the middle of an ArrayList shift objects over, or references over?

Question

Adding an element to the end of a Java ArrayList should take O(1) time. Adding an element to the middle, however, must shift over the right half by one to maintain order. This should take O(n) time (really O(n/2) simplified to O(n)).

My question is:

In the raw memory, does this shift move the objects themselves which reside in the ArrayList, or merely the references that point to them?

Regardless of which it is, the time complexity would be the same, but the overhead might be way different. Shifting a bunch of enormous objects to the side to make room for one in the middle might be a much larger operation than just shifting some int-sized references in memory.

So:

1. Which is it? I'm inclined to guess it's the references which are shifted, as a Java List holds references to objects on the heap which may be in any "order" in memory.

2. Any errors in my representation of everything above?

The reason I ask is purely theoretical. I just want to know what's going on in memory, if giant chunks of objects are being swapped around or if it's just references that are being shuffled over. Thanks.

(note: this is pretty much a follow up to this question which I asked earlier today.)

Answer 1

In the raw memory, does this shift move the objects themselves which reside in the ArrayList, or merely the references that point to them?

Short answer no real objects are moved, only the references are copied into internal array of arraylist with the new indexes.

Which is it? I'm inclined to guess it's the references which are shifted, as a Java List holds references to objects on the heap which may be in any "order" in memory.

Arraylist uses an array internally. References of objects are maintained in the array. Objects being pointed by these references can be anywhere in the memory, not necessarily in a sequential order as well. It is just the references in the arraylist internal array, which helps getting objects using array index.