The first test isn't surprising; three elements are removed off the end.
The second test is a bit surprising. Only two elements are removed. Why?
List iteration in Python essentially consists of an incrementing index into the list. When you delete an element you shift all the elements on the right over. This may cause the index to point to a different element.
Illustratively:
start of loop
[0,0,0,1,2,3,4,5,6]
^ <-- position of index
delete first element (since current element = 0)
[0,0,1,2,3,4,5,6]
^
next iteration
[0,0,1,2,3,4,5,6]
^
delete first element (since current element = 0)
[0,1,2,3,4,5,6]
^
and from now on no zeros are encountered, so no more elements are deleted.
To avoid confusion in the future, try not to modify lists while you're iterating over them. While Python won't complain (unlike dictionaries, which cannot be modified during iteration), it will result in weird and usually counterintuitive situations like this one.
Answer from nneonneo on Stack OverflowThe first test isn't surprising; three elements are removed off the end.
The second test is a bit surprising. Only two elements are removed. Why?
List iteration in Python essentially consists of an incrementing index into the list. When you delete an element you shift all the elements on the right over. This may cause the index to point to a different element.
Illustratively:
start of loop
[0,0,0,1,2,3,4,5,6]
^ <-- position of index
delete first element (since current element = 0)
[0,0,1,2,3,4,5,6]
^
next iteration
[0,0,1,2,3,4,5,6]
^
delete first element (since current element = 0)
[0,1,2,3,4,5,6]
^
and from now on no zeros are encountered, so no more elements are deleted.
To avoid confusion in the future, try not to modify lists while you're iterating over them. While Python won't complain (unlike dictionaries, which cannot be modified during iteration), it will result in weird and usually counterintuitive situations like this one.
since in list or Stack works in last in first out[LIFO] so pop() is used it removes last element in your list
where as pop(0) means it removes the element in the index that is first element of the list
as per the Docs
list.pop([i]):
Remove the item at the given position in the list, and return it. If no index is specified, a.pop() removes and returns the last item in the list. (The square brackets around the i in the method signature denote that the parameter is optional, not that you should type square brackets at that position. You will see this notation frequently in the Python Library Reference.)
When you grab the current node from the front of the queue in python BFS implementation, you are usually using pop(0) on an array. This requires a O(n) reshuffling. Wouldn’t this resolve to polynomial time complexity? If I am wrong, can someone explain why.
If we have a deque as : queue=collections.deque([0]) and list as : arr=[0].
Will queue.popleft() be faster ? Will arr.pop(0) be slower? Is there a difference in time complexity?
Yes. list.pop(0) is O(n), and deque.popleft() is O(1).
popleft is just a shortcut to pop(0), same way pop() is a shortcut to pop(len(sequence)-1), it's not suddenly performing a different operation with a different time complexity, as is also mentioned in the documentation
Indexed access is O(1) at both ends but slows to O(n) in the middle. For fast random access, use lists instead.
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.
To add to Martijn's answer, if you want a datastructure that has constant time pops at both ends, look at collections.deque.