Arrays, dynamic arrays and strings

An array stores items side by side in memory, like numbered boxes in a row. That is why reading or writing any position (index) is O(1). The price is that inserting or deleting in the middle means shifting everything after it, which is O(n).

A dynamic array grows itself when it fills up by moving to a bigger block of memory, so adding to the end is O(1) amortised. Examples are the Python list, Java ArrayList, C++ vector and JavaScript array. Strings behave like arrays of characters.

In Python, Java and JavaScript they cannot be changed once made, so building one with += in a loop copies the whole string every time. Collect the pieces in a list or builder and join them once at the end.