deque

A deque is an alternative implementation for lists. While the built-in list type is based on ordinary arrays, a deque is based on a doubly-linked list. Hence, a deque is much faster when you need to insert something into its middle or head, but much slower when you need to access an arbitrary index.

Of course, thanks to the overallocation of an internal array in the Python list type, not every list.append() call requires memory reallocation, and the average complexity of this method is O(1). Still, pops and appends are generally faster when performed on linked lists instead of arrays. The situation changes dramatically when the element needs to be added to an arbitrary point of sequence, however. Because all elements to the right of the new one need to be shifted in an array, the complexity of list.insert() is O(n). If you need to perform a lot of pops, appends, and inserts, the deque in place of list may provide substantial performance improvement. Remember to always profile your code before switching from list to deque, because a few things that are fast in arrays (such as accessing an arbitrary index) are extremely inefficient in linked lists.

For example, if we measure the time it takes to append one element and remove it from the sequence with timeit, the difference between list and deque may not be even noticeable, as follows:

$ python3 -m timeit \
> -s 'sequence=list(range(10))' \
> 'sequence.append(0); sequence.pop();'
1000000 loops, best of 3: 0.168 usec per loop
$ python3 -m timeit \ 
> -s 'from collections import deque; sequence=deque(range(10))' \
> 'sequence.append(0); sequence.pop();'
1000000 loops, best of 3: 0.168 usec per loop  

However, if we perform a similar comparison for situations where we want to add and remove the first element of the sequence, the performance difference is impressive, as follows:

$ python3 -m timeit \
> -s 'sequence=list(range(10))' \
> 'sequence.insert(0, 0); sequence.pop(0)'  
1000000 loops, best of 3: 0.392 usec per loop
$ python3 -m timeit \
> -s 'from collections import deque; sequence=deque(range(10))' \
> 'sequence.appendleft(0); sequence.popleft()'
10000000 loops, best of 3: 0.172 usec per loop
  

As you can see, the difference gets bigger as the size of the sequence grows. The following code snippet is an example of the same test performed on lists that contain 10,000 elements:

$ python3 -m timeit \
> -s 'sequence=list(range(10000))' \
> 'sequence.insert(0, 0); sequence.pop(0)'
100000 loops, best of 3: 14 usec per loop
$ python3 -m timeit \
> -s 'from collections import deque; sequence=deque(range(10000))' \ 
> 'sequence.appendleft(0); sequence.popleft()'
10000000 loops, best of 3: 0.168 usec per loop  

Thanks to the efficient append() and pop() methods, which work at the same speed from both ends of the sequence, deque makes a perfect example of implementing queues. For example, a First In First Out (FIFO) queue will be much more efficient if implemented with deque instead of list.

deque works well when implementing queues. Starting from Python 2.6, there is a separate queue module in Python's standard library that provides basic implementation for FIFO, LIFO, and priority queues. If you want to utilize queues as a mechanism of inter-thread communication, you should use classes from the queue module instead of collections.deque. This is because these classes provide all the necessary locking semantics. If you don't use threading and choose not to utilize queues as a communication mechanism, deque should be enough to provide queue implementation basics.