Is shifting required to pop the front of a list in Python?

Question

The python data strcutures page http://docs.python.org/tutorial/datastructures.html says

It is also possible to use a list as a queue, where the first element added is the first element retrieved (“first-in, first-out”); however, lists are not efficient for this purpose. While appends and pops from the end of list are fast, doing inserts or pops from the beginning of a list is slow (because all of the other elements have to be shifted by one).

I can understand why doing inserts at the front of the list would take be inefficient. But why does it say that popping the head / beginning of a list is slow? No shifting is required while doing a pop operation at the list -head right?

Answer 1

No shifting is required while doing a pop operation at the list -head right?

Think of a list as an array of references, where the first element of the list is always at array position zero. When you pop the first element of the list, you have to shift all the reference to the left by one position.

One could imagine alternative implementations, where popping the front of the list would be cheap (e.g. deque-style). I think we can trust the Python docs on this one, and assume that this is not how the built-in list class is implemented.

If you need efficient removals from the front of the container, use collections.deque:

Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.

Answer 2

Removing the first element usually involves moving all other elements so the former [1] element is at [0] after the removal. Of course a C-based implementation might just change a pointer so the array starts at the second element instead of the first, but then it would have to track how many elements are still available at the beginning of the list.