Why is the big O of pop() different from pop(0) in python

Question

Shouldn't they both be O(1), as popping an element from any location in a Python list involves destroying that list and creating one at a new memory location?

Answer 1

Python's list implementation uses a dynamically resized C array under the hood, removing elements usually requires you to move elements following after up to prevent gaps.

list.pop() with no arguments removes the last element. Accessing that element can be done in constant time. There are no elements following so nothing needs to be shifted.

list.pop(0) removes the first element. All remaining elements have to be shifted up one step, so that takes O(n) linear time.

Answer 2

To add to Martijn's answer, if you want a datastructure that has constant time pops at both ends, look at collections.deque.