03.3 - Advanced Collections

Theory 20 min Intermediate

The `collections` Module

Python's collections module provides specialized container data types that extend the built-ins with better performance or richer features.

from collections import (
    deque,
    Counter,
    defaultdict,
    OrderedDict,
    namedtuple,
    ChainMap
)

Class	Description	Replaces / Extends
`deque`	Double-ended queue	`list` with O(1) append/pop at both ends
`Counter`	Count occurrences	`dict` with counting helpers
`defaultdict`	Dict with default factory	`dict` with automatic defaults
`OrderedDict`	Preserves insertion order	`dict` (redundant in Python 3.7+, but extra features)
`namedtuple`	Tuple with named fields	`tuple`
`ChainMap`	Combine multiple dicts	Multiple dicts as one view

`deque` — Double-Ended Queue

A deque (pronounced "deck") supports O(1) append and pop from both ends. Lists are O(n) for operations at the front.

from collections import deque

# Create
q = deque([1, 2, 3, 4, 5])
q = deque(maxlen=5)   # fixed-size circular buffer

# Append
q.append(6)           # add to right
q.appendleft(0)       # add to left

# Pop
q.pop()               # remove from right
q.popleft()           # remove from left (O(1)!)

# Rotate
q = deque([1, 2, 3, 4, 5])
q.rotate(2)           # deque([4, 5, 1, 2, 3])
q.rotate(-1)          # rotate left

# Extend
q.extend([6, 7])
q.extendleft([0, -1])  # note: reverses order

Performance Comparison

Operation	`list`	`deque`
`append()` — right	O(1)	O(1)
`pop()` — right	O(1)	O(1)
`insert(0, x)` — left	O(n)	O(1)
`pop(0)` — left	O(n)	O(1)

Use deque when you need a queue (FIFO), a stack, or a sliding window.

# FIFO Queue
queue = deque()
queue.append("first")
queue.append("second")
queue.popleft()   # "first"

# Sliding window (last N items)
recent_events = deque(maxlen=10)
for event in stream:
    recent_events.append(event)   # old ones auto-dropped

`Counter` — Count Occurrences

Counter is a dict subclass for counting hashable objects.

from collections import Counter

# Count from an iterable
text = "the quick brown fox jumps over the lazy dog the fox"
word_count = Counter(text.split())
# Counter({'the': 3, 'fox': 2, 'quick': 1, ...})

# Count characters
char_count = Counter("mississippi")
# Counter({'s': 4, 'i': 4, 'p': 2, 'm': 1})

# Most common
word_count.most_common(3)
# [('the', 3), ('fox', 2), ('quick', 1)]

# Arithmetic
c1 = Counter(a=3, b=1)
c2 = Counter(a=1, b=2)
c1 + c2   # Counter({'a': 4, 'b': 3})
c1 - c2   # Counter({'a': 2})   (drops negatives)

# Access like dict
word_count["the"]   # 3
word_count["xyz"]   # 0  (not KeyError!)

# Total count
sum(word_count.values())   # 10
word_count.total()         # 10 (Python 3.10+)

`defaultdict` — Dict with Default Factory

defaultdict automatically creates a default value when a missing key is accessed.

from collections import defaultdict

# List factory — group items by key
groups = defaultdict(list)
data = [("fruits", "apple"), ("vegs", "carrot"), ("fruits", "banana")]
for category, item in data:
    groups[category].append(item)
# defaultdict(<class 'list'>, {'fruits': ['apple', 'banana'], 'vegs': ['carrot']})

# int factory — count without setdefault
word_count = defaultdict(int)
for word in "the quick brown fox the fox".split():
    word_count[word] += 1

# set factory — group unique items
tag_map = defaultdict(set)
for doc, tag in [("doc1", "python"), ("doc1", "data"), ("doc2", "python")]:
    tag_map[doc].add(tag)
# {"doc1": {"python", "data"}, "doc2": {"python"}}

# Custom factory
from functools import partial
empty_config = defaultdict(partial(dict, active=True, role="user"))

`OrderedDict`

In Python 3.7+, regular dicts preserve insertion order. OrderedDict still has extra methods:

from collections import OrderedDict

od = OrderedDict()
od["a"] = 1
od["b"] = 2
od["c"] = 3

# Move to end
od.move_to_end("a")        # moves "a" to last position
od.move_to_end("c", last=False)  # moves "c" to first position

# Pop from either end
od.popitem(last=True)      # remove last (like a stack)
od.popitem(last=False)     # remove first (like a queue)

`ChainMap` — Multiple Dicts as One

from collections import ChainMap

defaults = {"color": "blue", "size": "M", "debug": False}
user_settings = {"size": "L", "debug": True}
env_vars = {"color": "red"}

# Lookup order: env_vars → user_settings → defaults
config = ChainMap(env_vars, user_settings, defaults)
config["color"]   # "red"    (from env_vars)
config["size"]    # "L"      (from user_settings)
config["debug"]   # True     (from user_settings)

# Original dicts are NOT modified
config["color"] = "green"  # adds to env_vars

Choosing the Right Data Structure

Real-World Example: Log Analysis

from collections import Counter, defaultdict
from datetime import datetime

logs = [
    "2026-01-15 ERROR Database connection failed",
    "2026-01-15 INFO Server started",
    "2026-01-15 ERROR Disk space low",
    "2026-01-16 WARNING High memory usage",
    "2026-01-16 ERROR Database connection failed",
]

# Count by severity
severity_count = Counter(line.split()[1] for line in logs)
# Counter({'ERROR': 3, 'INFO': 1, 'WARNING': 1})

# Group by date
by_date = defaultdict(list)
for line in logs:
    parts = line.split(maxsplit=2)
    by_date[parts[0]].append(f"{parts[1]}: {parts[2]}")

# Most common errors
error_messages = Counter(
    line.split(maxsplit=2)[2]
    for line in logs
    if "ERROR" in line
)
error_messages.most_common(1)
# [('Database connection failed', 2)]

Key Vocabulary

Term	Definition
`deque`	Double-ended queue with O(1) append/pop at both ends
`Counter`	Dict subclass that counts occurrences of elements
`defaultdict`	Dict that auto-creates default values for missing keys
`ChainMap`	Groups multiple dicts into a single searchable view
O(1)	Constant time operation — performance doesn't grow with size
O(n)	Linear time — performance grows proportionally with size
Circular buffer	Fixed-size buffer that overwrites oldest items (`deque(maxlen=N)`)

Summary

deque replaces list when you need O(1) operations at both ends (queues, sliding windows)
Counter makes counting elements trivial — works with any iterable, supports arithmetic
defaultdict eliminates KeyError for missing keys with an automatic factory
OrderedDict.move_to_end() provides LRU-like ordering behavior
ChainMap creates a single view over multiple dicts with a defined lookup order
Always import from collections — these are in the standard library, no install needed

📄️ 03.1 - Lists & Tuples

Master Python's ordered sequences: lists (mutable) and tuples (immutable) — creation, indexing, slicing, methods, and use cases

📄️ 03.2 - Dicts & Sets

Master Python's key-value store (dict) and unique collection (set) — creation, operations, and real-world patterns