deque.popleft() is faster than list.pop(0), because the deque has been optimized to do popleft() approximately in O(1), while list.pop(0) takes O(n) (see deque objects).
Comments and code in _collectionsmodule.c for deque and listobject.c for list provide implementation insights to explain the performance differences. Namely that a deque object "is composed of a doubly-linked list", which effectively optimizes appends and pops at both ends, while list objects are not even singly-linked lists but C arrays (of pointers to elements (see Python 2.7 listobject.h#l22 and Python 3.5 listobject.h#l23), which makes them good for fast random access of elements but requires O(n) time to reposition all elements after removal of the first.
For Python 2.7 and 3.5, the URLs of these source code files are:
https://hg.python.org/cpython/file/2.7/Modules/_collectionsmodule.c
https://hg.python.org/cpython/file/2.7/Objects/listobject.c
https://hg.python.org/cpython/file/3.5/Modules/_collectionsmodule.c
https://hg.python.org/cpython/file/3.5/Objects/listobject.c
Using %timeit, the performance difference between deque.popleft() and list.pop(0) is about a factor of 4 when both the deque and the list have the same 52 elements and grows to over a factor of 1000 when their lengths are 10**8. Test results are given below.
import string
from collections import deque
%timeit d = deque(string.letters); d.popleft()
1000000 loops, best of 3: 1.46 µs per loop
%timeit d = deque(string.letters)
1000000 loops, best of 3: 1.4 µs per loop
%timeit l = list(string.letters); l.pop(0)
1000000 loops, best of 3: 1.47 µs per loop
%timeit l = list(string.letters);
1000000 loops, best of 3: 1.22 µs per loop
d = deque(range(100000000))
%timeit d.popleft()
10000000 loops, best of 3: 90.5 ns per loop
l = range(100000000)
%timeit l.pop(0)
10 loops, best of 3: 93.4 ms per loop
Videos
deque.popleft() is faster than list.pop(0), because the deque has been optimized to do popleft() approximately in O(1), while list.pop(0) takes O(n) (see deque objects).
Comments and code in _collectionsmodule.c for deque and listobject.c for list provide implementation insights to explain the performance differences. Namely that a deque object "is composed of a doubly-linked list", which effectively optimizes appends and pops at both ends, while list objects are not even singly-linked lists but C arrays (of pointers to elements (see Python 2.7 listobject.h#l22 and Python 3.5 listobject.h#l23), which makes them good for fast random access of elements but requires O(n) time to reposition all elements after removal of the first.
For Python 2.7 and 3.5, the URLs of these source code files are:
https://hg.python.org/cpython/file/2.7/Modules/_collectionsmodule.c
https://hg.python.org/cpython/file/2.7/Objects/listobject.c
https://hg.python.org/cpython/file/3.5/Modules/_collectionsmodule.c
https://hg.python.org/cpython/file/3.5/Objects/listobject.c
Using %timeit, the performance difference between deque.popleft() and list.pop(0) is about a factor of 4 when both the deque and the list have the same 52 elements and grows to over a factor of 1000 when their lengths are 10**8. Test results are given below.
import string
from collections import deque
%timeit d = deque(string.letters); d.popleft()
1000000 loops, best of 3: 1.46 µs per loop
%timeit d = deque(string.letters)
1000000 loops, best of 3: 1.4 µs per loop
%timeit l = list(string.letters); l.pop(0)
1000000 loops, best of 3: 1.47 µs per loop
%timeit l = list(string.letters);
1000000 loops, best of 3: 1.22 µs per loop
d = deque(range(100000000))
%timeit d.popleft()
10000000 loops, best of 3: 90.5 ns per loop
l = range(100000000)
%timeit l.pop(0)
10 loops, best of 3: 93.4 ms per loop
Is there performance difference?
Yes. deque.popleft() is O(1) -- a constant time operation. While list.pop(0) is O(n) -- linear time operation: the larger the list the longer it takes.
Why?
CPython list implementation is array-based. pop(0) removes the first item from the list and it requires to shift left len(lst) - 1 items to fill the gap.
deque() implementation uses a doubly linked list. No matter how large the deque, deque.popleft() requires a constant (limited above) number of operations.
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.