Why filling an array from the front is slow?

Question

In the chapter on Arrays in the book Elements of Programming Interviews in Python, it is mentioned that Filling an array from the front is slow, so see if it’s possible to write values from the back.

What could be the possible reason for that?

Answer 1

Python lists, at least in CPython, the standard Python implementation, are actually implemented from a data structure perspective as arrays, not lists.

However, these are dynamically allocated and resized, so appending to the end of a Python-list is actually possible. It takes a somewhat variable amount of time to do so: CPython tries to allocate additional space when items are being appended beyond what is actually necessary, such that it doesn't need to allocate more space for every append operation. At best, appending, if space has already been allocated, is O(1), and since it is an array, indexing is also O(1).

What will take a long time, however, is adding something to the beginning of a list, as this would require shifting all the array values, and is O(n), just as popping the first element is.

Python language designers have decided to call these arrays lists instead of arrays, contradicting standard terminology, in part, I assume, because the dynamic resizing makes them different from standard, fixed-size lists.

Unless I'm mistaken, collections.deque implements a doubly-linked list, with the corresponding O(1) appends/pops on either side, and so on.