Python: Collections Module

deque: Double-ended Queue

A deque (pronounced "deck") is a generalisation of stacks and queues that supports efficient appending and popping from both ends. Appending or removing from either end of a deque is O(1), whereas inserting or removing from the left end of a Python list is O(n) because every other element must shift. This makes deque the correct choice for implementing queues, sliding-window algorithms, and breadth-first search frontiers.

You can create a bounded deque by passing a maxlen argument. A bounded deque automatically discards items from the opposite end when new ones are added past the limit, which is exactly what you need for a rolling history or a fixed-size cache.

OrderedDict

Since Python 3.7, regular dictionaries maintain insertion order as part of the language specification. So why use OrderedDict? The difference lies in equality semantics and the move_to_end() method. Two regular dicts with the same keys and values are always equal regardless of insertion order. Two OrderedDict objects are equal only if they have the same keys and values in the same order.

move_to_end(key, last=True) moves an existing key to the rightmost position (or leftmost if last=False) without re-inserting it. This operation is O(1) and is the key building block for implementing an LRU (Least Recently Used) cache from scratch.

defaultdict

A defaultdict is a subclass of dict that takes a default_factorycallable as its first argument. When you access a key that does not exist, instead of raising a KeyError, it calls default_factory() with no arguments, stores the result under the missing key, and returns it. This eliminates the boilerplate pattern of checking for a key, initialising it if absent, and then updating it.

Common factory choices are list (for grouping), int (for counting, since int() returns 0), set (for collecting unique items per group), anddict (for nested mappings). You can also pass a lambda for a custom default value.

Counter

Counter is a specialised dict subclass designed for counting hashable objects. It accepts an iterable or a mapping, counts each element, and stores the counts as dictionary values. Missing keys return 0 rather than raising KeyError. Beyond being a convenient counting tool, Counter supports arithmetic operations: addition combines two counters, subtraction removes counts, intersection takes the minimum of each count, and union takes the maximum.

namedtuple

A namedtuple is a tuple subclass whose fields have names. It occupies the same memory as a plain tuple and supports all tuple operations, but fields can also be accessed by name. This makes code far more readable: point.x is clearer thanpoint[0], and the named type appears in error messages and repr output. Named tuples are immutable, which makes them safe to use as dictionary keys and in sets.

Python 3.6 introduced typing.NamedTuple, which provides a class-based syntax with optional type annotations and default values, while producing the same efficient tuple-backed objects. Use the class syntax for new code; the functional formcollections.namedtuple() is still common in older codebases and libraries.

ChainMap

ChainMap groups multiple dictionaries into a single logical view without copying them. Lookups search each mapping in order until a key is found. Writes, updates, and deletions go to the first mapping only. This makes ChainMap a natural fit for layered configuration systems: user settings override application defaults, which override system defaults, without merging the dicts or duplicating data.

UserDict, UserList, and UserString

When you subclass dict, list, or str directly and override methods, you sometimes find that built-in C-level methods call each other's original implementations rather than your overrides. UserDict, UserList, andUserString from collections are pure-Python wrappers around these types that store their data in a plain attribute (self.data for UserDict andUserList, self.data for UserString). Overriding methods on these wrappers is safe and predictable.

heapq: Min-Heap and Max-Heap

The heapq module provides an efficient implementation of the heap queue algorithm (also called a priority queue) operating on ordinary Python lists. It maintains the heap invariant: heap[0] is always the smallest element, and for any indexk, heap[k] is smaller than or equal to heap[2*k+1] andheap[2*k+2]. Push and pop operations are O(log n). Peeking at the smallest element is O(1).

Python's heap is a min-heap. To simulate a max-heap, negate the values before pushing and negate again when popping. For complex objects, use tuples where the first element is the priority value.

bisect: Sorted List Operations

The bisect module uses binary search to locate an insertion point in a sorted list in O(log n) time. bisect_left(a, x) returns the leftmost position wherex can be inserted while keeping a sorted, placing it before any existing equal elements. bisect_right(a, x) (also aliased as bisect(a, x)) returns the rightmost such position, placing it after any equal elements.

insort_left(a, x) and insort_right(a, x) insert x into the list at the correct position to keep it sorted. Since insertion into the middle of a list is O(n), use these with care on large lists. The module's core value is in fast searching and grade-range lookups, not bulk insertion.

array Module: Typed Arrays

Python's built-in list can hold objects of any type, which is flexible but memory-heavy. Each element in a list is a full Python object with reference counting overhead. Thearray module provides a typed array that stores elements in a compact binary format, similar to a C array. All elements must share the same type, specified by a single-character type code at creation time.

Use array when you need to store a large sequence of numbers and want to reduce memory consumption without pulling in a third-party dependency like NumPy. It also has fast conversion to and from bytes, making it useful for binary file I/O and network protocol work.

queue.Queue, queue.LifoQueue, and queue.PriorityQueue

The queue module provides three thread-safe queue implementations designed for use in multithreaded programs. Unlike collections.deque, these queues handle locking internally, so multiple threads can safely call put() and get()concurrently without data corruption. They also support blocking with optional timeouts, which is the standard way to coordinate producer and consumer threads.

queue.Queue is a first-in, first-out queue. queue.LifoQueue is a last-in, first-out stack. queue.PriorityQueue retrieves items in priority order, where the item with the lowest value (using Python's standard comparison) comes out first. All three have the same interface: put(item), get(),task_done(), and join().

Quiz - Test Your Knowledge

Ten questions covering the data structures and modules in this tutorial: deque performance characteristics, OrderedDict ordering semantics, defaultdict behaviour, Counter arithmetic, namedtuple access patterns, ChainMap write rules, UserDict subclassing rationale, heap invariants, bisect insertion points, and thread-safe queue retrieval order.