Arrays and dynamic arrays

An array stores items side by side in memory, in one contiguous block. That is why reading or writing any index is O(1): the address is just the start plus the index times the item size. The cost is that inserting or deleting in the middle shifts everything after it, which is O(n).

The list type you already use (Python list, JavaScript array, Java ArrayList, C++ vector, C# List) is a dynamic array. When it is full, it grabs a bigger block of memory, typically 1.5 to 2 times larger, and copies everything across. That copy is rare enough that appending at the end is O(1) on average, which is called amortised cost. Removing from the front, though, is O(n) every time, a common hidden cost.