Why is list pop(0) not an O(1) operation in python?

Question

l = [1,2,3,4]

popping the last element would be an O(1) operation since:

1. It returns the last element
2. Changes a few fixed attributes like len of the list

Why can't we do the same with pop(0)?

1. Return the first element
2. Change the pointer of the first element (index 0) to that of the second element (index 1) and change a few fixed attributes?

Answer 1

Lists could have been implemented to do what you suggest, but it would add complexity and overhead, for an operation better handled by collections.deque. All lists everywhere would need extra metadata to track how much empty space is at the front (important for handling the resize policy, and calling free on the right pointer when the list dies or gets resized), and the logic for when and how to resize would also become more complicated.

The tradeoff was not deemed worthwhile.