Arrays: Insert

Task: Insert 25 at index position 2

// ArrayList.add(k, v), insidefor (int i = size; i > k; i--) {    a[i] = a[i - 1];   // shift right}a[k] = v;size++;

What you are watching

A dynamic array - an ArrayList, a vector, a Python list - is a plain array with spare capacity at the end. This one holds five values in room for six. Inserting 25 at index 2 still has to make a gap: 30, 40 and 50 each move one place right, starting from the back so nothing is overwritten before it has been copied. Only then is index 2 free. The spare capacity is what lets the array grow at all; it does nothing about the shifting, which is why inserting into the middle stays expensive.