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

Question

This question already has an answer here:

• What is the time complexity of popping elements from list in Python? 4 answers

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

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

Answer 2

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.