title: Does inserting into the middle of an ArrayList shift objects over, or references over?
body: <p>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)).</p>
  
  <p>My question is:</p>
  
  <p>In the raw memory, does this shift move the <em>objects themselves</em> which reside in the ArrayList, or merely the references that point to them?</p>
  
  <p>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.</p>
  
  <p>So:</p>
  
  <ol>
  <li><p>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.</p></li>
  <li><p>Any errors in my representation of everything above?</p></li>
  </ol>
  
  <p>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.</p>
  
  <p>(note: this is pretty much a follow up to <a href="https://stackoverflow.com/questions/32381773/arrays-in-different-languages-store-references-or-raw-objects">this question</a> which I asked earlier today.)</p>