Why is appending to a Python list constant time while inserting at position zero is linear, and what code shows the difference?
Because the list keeps some room spare, and adding to the end only uses that room. Putting something at the front has to move everything else along.
from collections import deque
stack = [1, 2, 3, 4, 5]
# Adding to the front. Everything else moves along by one place.
stack.insert(0, 0)
print(stack) # [0, 1, 2, 3, 4, 5]
# Adding to the back. Nothing has to move.
stack.append(6)
print(stack) # [0, 1, 2, 3, 4, 5, 6]
So what is happening inside the list? A Python list is really a block of memory with a length, and it keeps some room spare at the end so that adding one more item does not have to find a new block every time. When the spare room runs out, the list takes a bigger block, copies everything across, and carries on. That copy is the expensive part, and it does not happen every time.
Putting an item at the front is different, because the front is where the first item lives. To make room, every other item has to move one place along. That is n steps, every single time, so it is O of n.
There is a detail worth knowing here, and it is about the class deque. It is built for adding and removing at both ends, and it does that in O of 1 without the copying. So if your code is putting things on the front of a list over and over, that is a sign that you want a deque instead.
The next question in this topic looks at lookups.