Collections Module

Difficulty: Intermediate

Question

What useful data structures does the collections module provide?

Answer

The collections module provides specialized container types that extend Python's built-in dict, list, set, and tuple.

Key classes: - Counter: dict subclass for counting hashable objects - defaultdict: dict with a factory for missing keys - deque: double-ended queue with O(1) append/pop from both ends - namedtuple: tuple subclass with named fields - OrderedDict: dict that remembers insertion order (relevant pre-3.7) - ChainMap: groups multiple dicts into a single view

These are often the right answer to interview coding problems because they simplify common patterns.

Code examples

deque: Double-Ended Queue

from collections import deque

# deque vs list for queue operations
d = deque([1, 2, 3])

d.append(4)       # Right end: [1, 2, 3, 4]
d.appendleft(0)   # Left end: [0, 1, 2, 3, 4]
d.pop()           # Right: 4, deque is [0, 1, 2, 3]
d.popleft()       # Left: 0, deque is [1, 2, 3]
print(d)

# Rotation
d = deque([1, 2, 3, 4, 5])
d.rotate(2)   # Rotate right by 2
print(d)      # deque([4, 5, 1, 2, 3])
d.rotate(-2)  # Rotate left by 2
print(d)      # deque([1, 2, 3, 4, 5])

# Fixed-size deque (sliding window)
recent = deque(maxlen=3)
for i in range(5):
    recent.append(i)
    print(f"Added {i}: {list(recent)}")

# Performance: deque vs list
import time
n = 100_000

lst = []
start = time.time()
for i in range(n):
    lst.insert(0, i)  # O(n) each time!
print(f"List insert(0): {time.time() - start:.4f}s")

d = deque()
start = time.time()
for i in range(n):
    d.appendleft(i)   # O(1) each time
print(f"Deque appendleft: {time.time() - start:.4f}s")

deque provides O(1) operations on both ends, while list.insert(0) is O(n). maxlen creates a sliding window that automatically drops old items.

Counter: Counting Made Easy

from collections import Counter

# Count anything hashable
words = 'the quick brown fox jumps over the lazy dog the fox'.split()
word_count = Counter(words)
print(word_count)
print(word_count.most_common(3))  # Top 3

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

print(inventory_a + inventory_b)  # Add counts
print(inventory_a - inventory_b)  # Subtract (drops zero/negative)
print(inventory_a & inventory_b)  # Minimum of each
print(inventory_a | inventory_b)  # Maximum of each

# Practical: find most common character
def most_common_char(s):
    counter = Counter(s.lower().replace(' ', ''))
    return counter.most_common(1)[0]

char, count = most_common_char("Hello World")
print(f"Most common: '{char}' ({count} times)")

# Check if one is subset of another (anagram check)
def is_anagram(s1, s2):
    return Counter(s1.lower().replace(' ', '')) == Counter(s2.lower().replace(' ', ''))

print(is_anagram('listen', 'silent'))  # True

Counter is invaluable for interview problems: frequency counting, anagram checking, top-k problems, and inventory management.

namedtuple and ChainMap

from collections import namedtuple, ChainMap

# namedtuple: lightweight, immutable class
Point = namedtuple('Point', ['x', 'y'])
p = Point(3, 4)
print(p.x, p.y)          # 3 4 (access by name)
print(p[0], p[1])        # 3 4 (access by index)
x, y = p                 # Unpacking works
print(f"({x}, {y})")

# Convert to dict
print(p._asdict())        # {'x': 3, 'y': 4}

# Create from dict
data = {'x': 10, 'y': 20}
p2 = Point(data)
print(p2)                 # Point(x=10, y=20)

# namedtuple with defaults (Python 3.6.1+)
Config = namedtuple('Config', ['host', 'port', 'debug'], defaults=['localhost', 8080, False])
print(Config())           # Config(host='localhost', port=8080, debug=False)
print(Config('0.0.0.0'))  # Config(host='0.0.0.0', port=8080, debug=False)

# ChainMap: layered dict lookup
defaults = {'color': 'blue', 'size': 'medium', 'font': 'Arial'}
user_prefs = {'color': 'red'}
env_overrides = {'size': 'large'}

config = ChainMap(env_overrides, user_prefs, defaults)
print(config['color'])  # 'red' (from user_prefs)
print(config['size'])   # 'large' (from env_overrides)
print(config['font'])   # 'Arial' (from defaults)

namedtuple creates readable, immutable records. ChainMap provides a layered lookup - first dict found wins. Both are used extensively in production code.

Key points

For Python 3.7+, consider typing.NamedTuple or @dataclass instead of namedtuple
deque is thread-safe for append/pop operations (uses GIL-protected C implementation)
Counter.elements() returns an iterator over elements, repeating each as many times as its count

Concepts covered

Counter, defaultdict, deque, namedtuple, OrderedDict, ChainMap