title: Java: ArrayList add() and remove() performance, implementation?
body: <p>I have read somewhere that ArrayList's <em>add()</em> and <em>remove()</em> operations run in "amortized constant" time. What does this mean exactly?</p>
  
  <p>In the implementation of <em>add(item)</em> I can see that it ArrayList uses an array buffer, which is at most 3/2 of the list't size, and if it is full, <em>System.arraycopy()</em> is called, which should execute in O(n), not O(1) time. Is it then that System.arraycopy attempts to do something smarter than copying elements one by one into newly created array, since the time is actually O(1)?</p>
  
  <hr>
  
  <p>Conclusion: <em>add(item)</em> runs in amortized constant time, but <em>add(item, index)</em> and <em>remove(index)</em> don't, they run in linear time (as explained in answers).</p>