collections: deque, Counter, defaultdict & namedtuple

Python’s built-in collections module provides specialized container data structures designed for specific algorithmic workloads. Beyond basic lists and dicts, using deque, Counter, defaultdict, ChainMap, and namedtuple improves algorithmic performance, eliminates key management boilerplate, and reduces memory overhead.

This chapter details collections.deque block array mechanics, Counter multi-set mathematics, defaultdict missing key hooks (__missing__), and ChainMap lookup chains.

1. `collections.deque` Architecture (Block Array Mechanics)

A collections.deque (double-ended queue) is not a traditional single-node doubly linked list. In CPython, it is implemented as a doubly linked list of fixed-size memory blocks (each block holding 64 element pointers):

#define BLOCKLEN 64

typedef struct _block {
    struct _block *leftlink;
    struct _block *rightlink;
    PyObject *data[BLOCKLEN];
} block;

typedef struct {
    PyObject_VAR_HEAD
    block *leftblock;
    block *rightblock;
    size_t leftindex;
    size_t rightindex;
    // ...
} dequeobject;

CPython deque Memory Block Architecture:

[ Left Block (64 Slots) ] <---> [ Middle Block (64 Slots) ] <---> [ Right Block (64 Slots) ]
  ^                                                                 ^
  |                                                                 |
leftindex (popleft/appendleft)                                   rightindex (pop/append)

Performance Invariants:

Head & Tail Operations (append, appendleft, pop, popleft): $O(1)$ constant time. Pushing or popping at either end modifies block indices without shifting surrounding elements.
Random Access (deque[i]): $O(N)$ linear time. Accessing middle elements requires traversing block links from the nearest end.

2. `defaultdict` & The `missing` Protocol

defaultdict inherits from dict and overrides the __missing__(key) dunder method:

When a key is missing during bracket access (d[key]):

dict.__getitem__ fails to find the key.
It delegates to __missing__(key).
defaultdict calls its default_factory callable (e.g. list, int, set), inserts the returned value into the dict, and returns it.

Gotcha: d.get(missing_key) does NOT invoke __missing__() and will return None or the specified default without inserting the key into the dictionary!

3. `Counter` Multi-set Mathematics

Counter is a dict subclass designed for counting hashable objects. It supports multiset mathematical operations:

from collections import Counter

inventory_a = Counter(apples=5, bananas=2)
inventory_b = Counter(apples=3, bananas=4, oranges=1)

# Multiset Addition & Subtraction
total = inventory_a + inventory_b       # Counter({'apples': 8, 'bananas': 6, 'oranges': 1})
difference = inventory_a - inventory_b  # Counter({'apples': 2}) (Strips zero and negative counts!)
intersection = inventory_a & inventory_b # Counter({'apples': 3, 'bananas': 2}) (Takes min count)

4. `ChainMap` Scope Lookup & `namedtuple` Memory

ChainMap: Groups multiple dictionaries into a single updateable view without copying data. Lookups scan dictionaries sequentially (maps[0] $\rightarrow$ maps[1]), making it ideal for nested configuration stacks and scope chains.
namedtuple: Creates tuple subclasses with named fields. Consumes zero extra memory over standard tuples while improving code readability.

⚡

Revision Mode Active Condensed for 5-minute review. Focused on 30-second pitches, mental anchors, and high-frequency interview traps.

⚡ 30-Second Elevator Pitch

“The collections module provides specialized containers: deque uses a doubly linked list of 64-element blocks for O(1) head/tail pushes/pops. defaultdict automates missing key initialization via the __missing__ protocol. Counter enables multiset arithmetic, while ChainMap chains multiple dictionaries into a single prioritized configuration view without data copying.”

🧠 Under The Hood & Mental Model

deque Block Chains: 64-element block arrays combine $O(1)$ end pushes/pops with cache-friendly memory locality.
__missing__ Protocol: Executed exclusively by d[key] on missing keys; ignored by d.get().
Counter Multiset Math: Addition, subtraction (-), and intersection (&) automatically filter out zero and negative counts.
ChainMap View: Searches underlying dicts sequentially without copying key-value payloads into a new mapping.

💻 High-Yield Code & Gotcha

# ❌ ANTI-PATTERN: Manual Key Initialization in Nested Dictionaries
data = {}
for category, item in items:
    if category not in data:
        data[category] = []
    data[category].append(item)

# ✅ PRODUCTION PATTERN: Idiomatic defaultdict Grouping
from collections import defaultdict

data = defaultdict(list)
for category, item in items:
    data[category].append(item) # Automatically initializes missing keys with empty list!

⚠️ GOTCHA: `defaultdict.get()` Missing Key Bypass

from collections import defaultdict

d = defaultdict(list)
val = d.get("missing_key")  # GOTCHA: Returns None! DOES NOT invoke default_factory!
print("missing_key" in d)   # False! Key was NOT inserted into dict!

val_correct = d["missing_key"] # Invokes __missing__! Inserts [] into dict.
print("missing_key" in d)       # True!

⚖️ Trade-Offs & Comparison

+ deque vs list: $O(1)$ push/pop at both ends vs $O(N)$ front pop for list.
- deque Indexing: $O(N)$ random access lookup vs $O(1)$ indexing for list. Use list when indexing middle positions frequently.

🌟 My Experience (STAR Anchor)

“A web crawler service suffered thread contention when managing task queues using lists. Replacing list.pop(0) with collections.deque.popleft() and grouping scraped domains via defaultdict(set) eliminated queue lock contention and reduced scraping memory overhead by 40%.”

Python Interview Handbook

collections: deque, Counter, defaultdict & namedtuple

1. `collections.deque` Architecture (Block Array Mechanics)

Performance Invariants:

2. `defaultdict` & The `missing` Protocol

3. `Counter` Multi-set Mathematics

4. `ChainMap` Scope Lookup & `namedtuple` Memory

⚡ 30-Second Elevator Pitch

🧠 Under The Hood & Mental Model

💻 High-Yield Code & Gotcha

⚠️ GOTCHA: `defaultdict.get()` Missing Key Bypass

⚖️ Trade-Offs & Comparison

🌟 My Experience (STAR Anchor)

How is `collections.deque` implemented internally in CPython, and how does its performance differ from `list`?

No Interactive Questions Yet

collections: deque, Counter, defaultdict & namedtuple

1. collections.deque Architecture (Block Array Mechanics)

Performance Invariants:

2. defaultdict & The __missing__ Protocol

3. Counter Multi-set Mathematics

4. ChainMap Scope Lookup & namedtuple Memory

⚡ 30-Second Elevator Pitch

🧠 Under The Hood & Mental Model

💻 High-Yield Code & Gotcha

⚠️ GOTCHA: defaultdict.get() Missing Key Bypass

⚖️ Trade-Offs & Comparison

🌟 My Experience (STAR Anchor)

How is `collections.deque` implemented internally in CPython, and how does its performance differ from `list`?

No Interactive Questions Yet

1. `collections.deque` Architecture (Block Array Mechanics)

2. `defaultdict` & The `missing` Protocol

3. `Counter` Multi-set Mathematics

4. `ChainMap` Scope Lookup & `namedtuple` Memory

⚠️ GOTCHA: `defaultdict.get()` Missing Key Bypass