Using collections

The collections module provides high-performance alternatives to the built-in container types. The main types available in this module are:

• deque: A list-like type with extra features
• defaultdict: A dict-like type with a built-in default factory feature
• namedtuple: A tuple-like type that assigns keys for members

deque

A deque is an alternative implementation for lists. While a list is based on 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 on arbitrary point of sequence. Because...