Arrays

An array refers to a data type that designates a size and allocates that amount of continuous memory space. The size is fixed, and once an array is created, its size cannot be changed.

Most dynamic programming languages don't even have static arrays. Python does not provide static arrays either, only offering dynamic arrays in the form of lists.

In the worst case, insertion becomes $O(n)$, but since this does not happen often, the Amortized Insertion Time is still $O(1)$.

Tips:

If indices are not important, consider sorting. If indices are important, consider using two pointers.