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?
Asked
Active
Viewed 1.8k times
10
Mike Müller
- 82,630
- 20
- 166
- 161
Teererai Marange
- 2,044
- 4
- 32
- 50
-
1@thefourtheye *in a python list* – Padraic Cunningham Jan 06 '16 at 12:30
2 Answers
29
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.
Martijn Pieters
- 1,048,767
- 296
- 4,058
- 3,343
-
why isnt pop(0) O(1)? Can we not just shift the memory pointer of the 0th element of the list up by 1? Like, after pop(0) I just say that my new list starts from its 1st element – figs_and_nuts Aug 21 '23 at 01:43
-
@figs_and_nuts because a Python list is not just that C array, it is a *dynamic resized* array. Removing from the front would wreak havoc with the dynamic resizing. Shifting everything down means that when the list size drops below a threshold reallocating the chunk freed at the end a lot simpler. Not to mention what handling a mix of pop(0) and append operations would do. – Martijn Pieters Aug 21 '23 at 07:49
10
To add to Martijn's answer, if you want a datastructure that has constant time pops at both ends, look at collections.deque.
Daniel Roseman
- 588,541
- 66
- 880
- 895