Advanced Data Structures and Collections

Overview#

Beyond the core list, tuple, dict, and set, Python's standard library provides specialized data structures that solve common performance and design problems far more efficiently than hand-rolled solutions. This notebook goes deep into the collections module (deque, defaultdict, Counter, OrderedDict, ChainMap, namedtuple), the heapq module for priority queues, the bisect module for fast sorted-list operations, and the array module for memory-efficient numeric storage. Knowing when to reach for these instead of a plain list or dict is a mark of experienced Python code.

1. deque: Double-Ended Queue#

A list is fast for appending/popping at the end, but slow (O(n)) for operations at the beginning, since every remaining element has to shift. collections.deque (pronounced "deck") is optimized for fast appends and pops from both ends, in O(1) time.

Python 3.12 (WASM)
EditCopyAsk AIRun Code
from collections import deque

d = deque([1, 2, 3])

d.append(4)          # add to the right: deque([1, 2, 3, 4])
d.appendleft(0)        # add to the left:  deque([0, 1, 2, 3, 4])

d.pop()                 # remove from the right, returns 4
d.popleft()               # remove from the left, returns 0

print(d)                   # deque([1, 2, 3])

Use case: a sliding window / fixed-size history#

Python 3.12 (WASM)
EditCopyAsk AIRun Code
from collections import deque

recent_events = deque(maxlen=3)   # automatically discards the oldest item

for event in ["login", "click", "scroll", "purchase", "logout"]:
    recent_events.append(event)
    print(list(recent_events))

# ['login']
# ['login', 'click']
# ['login', 'click', 'scroll']
# ['click', 'scroll', 'purchase']    <- 'login' dropped automatically
# ['scroll', 'purchase', 'logout']

Use case: implementing a queue (FIFO) or a stack (LIFO)#

Python 3.12 (WASM)
EditCopyAsk AIRun Code
# Queue: first in, first out
queue = deque()
queue.append("task1")
queue.append("task2")
print(queue.popleft())   # task1 — processed in arrival order

# Stack: last in, first out
stack = deque()
stack.append("page1")
stack.append("page2")
print(stack.pop())        # page2 — most recent first

deque is generally preferable to a plain list whenever you need queue- like or stack-like behavior with frequent additions/removals from the front.

2. Counter: Counting Made Easy#

Python 3.12 (WASM)
EditCopyAsk AIRun Code
from collections import Counter

votes = ["red", "blue", "red", "green", "blue", "red"]
tally = Counter(votes)

print(tally)                  # Counter({'red': 3, 'blue': 2, 'green': 1})
print(tally["red"])            # 3
print(tally["purple"])          # 0 — missing keys default to 0, no KeyError
print(tally.most_common(2))      # [('red', 3), ('blue', 2)]

# Counter arithmetic
a = Counter(["a", "b", "b"])
b = Counter(["b", "c"])
print(a + b)   # Counter({'b': 3, 'a': 1, 'c': 1})
print(a - b)   # Counter({'a': 1, 'b': 1})  (keeps only positive counts)

# Counting characters in a string
letter_counts = Counter("mississippi")
print(letter_counts)   # Counter({'i': 4, 's': 4, 'p': 2, 'm': 1})

3. defaultdict: Dictionaries with Automatic Defaults#

Python 3.12 (WASM)
EditCopyAsk AIRun Code
from collections import defaultdict

# Grouping items by a key, without manually checking if the key exists
word_groups = defaultdict(list)
for word in ["apple", "avocado", "banana", "blueberry", "cherry"]:
    word_groups[word[0]].append(word)

print(dict(word_groups))
# {'a': ['apple', 'avocado'], 'b': ['banana', 'blueberry'], 'c': ['cherry']}

# Counting occurrences manually (Counter is usually better for this specific case)
counts = defaultdict(int)
for word in ["a", "b", "a", "c"]:
    counts[word] += 1
print(dict(counts))   # {'a': 2, 'b': 1, 'c': 1}

# Building a nested structure
tree = defaultdict(lambda: defaultdict(list))
tree["fruits"]["citrus"].append("orange")
tree["fruits"]["citrus"].append("lemon")

The factory function passed to defaultdict (list, int, or a custom lambda) is called automatically whenever a missing key is accessed, producing a sensible starting value instead of raising KeyError.

4. OrderedDict: Dictionaries with Extra Ordering Features#

Since Python 3.7, regular dict already preserves insertion order, so OrderedDict is less essential than it used to be — but it still offers a few extra capabilities regular dicts don't.

Python 3.12 (WASM)
EditCopyAsk AIRun Code
from collections import OrderedDict

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

od.move_to_end("a")              # moves 'a' to the end
print(list(od.keys()))            # ['b', 'c', 'a']

od.move_to_end("c", last=False)   # moves 'c' to the beginning
print(list(od.keys()))            # ['c', 'b', 'a']

# Equality comparison is order-sensitive for OrderedDict, unlike plain dict
print(OrderedDict(a=1, b=2) == OrderedDict(b=2, a=1))   # False
print({"a": 1, "b": 2} == {"b": 2, "a": 1})                # True — order ignored

5. ChainMap: Combining Multiple Dictionaries#

ChainMap groups multiple dictionaries into a single view, searched in order, without actually merging or copying them. This is especially handy for layered configuration (defaults, overridden by environment, overridden by command-line args).

Python 3.12 (WASM)
EditCopyAsk AIRun Code
from collections import ChainMap

defaults = {"theme": "light", "timeout": 30}
user_settings = {"theme": "dark"}

config = ChainMap(user_settings, defaults)   # searched left to right

print(config["theme"])      # dark    (found in user_settings first)
print(config["timeout"])     # 30       (not in user_settings, falls back to defaults)

config["timeout"] = 60        # writes go to the FIRST mapping only
print(user_settings)           # {'theme': 'dark', 'timeout': 60}
print(defaults)                 # {'theme': 'light', 'timeout': 30} — unchanged

6. namedtuple: Lightweight, Readable Records#

Covered briefly in the Data Structures notebook, namedtuple deserves a closer look as a genuinely useful tool for structured data without the overhead of a full class.

Python 3.12 (WASM)
EditCopyAsk AIRun Code
from collections import namedtuple

Point = namedtuple("Point", ["x", "y"])
Employee = namedtuple("Employee", "name role salary")   # space-separated also works

p = Point(3, 4)
print(p.x, p.y)          # 3 4
print(p[0], p[1])         # 3 4 — still supports tuple-style indexing

e = Employee("Priya", "Engineer", 90000)
print(e.name)              # Priya

# Convert to a dict when needed
print(e._asdict())          # {'name': 'Priya', 'role': 'Engineer', 'salary': 90000}

# Create a modified copy (namedtuples are still immutable)
e2 = e._replace(salary=95000)
print(e2)   # Employee(name='Priya', role='Engineer', salary=95000)

For more complex cases needing default values and type hints together, typing.NamedTuple offers a class-based syntax:

Python 3.12 (WASM)
EditCopyAsk AIRun Code
from typing import NamedTuple

class Point(NamedTuple):
    x: float
    y: float
    label: str = "unnamed"

p = Point(1.0, 2.0)
print(p)   # Point(x=1.0, y=2.0, label='unnamed')

7. heapq: Priority Queues#

A heap is a tree-based structure that keeps the smallest (or largest) element quickly accessible. heapq implements a min-heap using a plain list, giving O(log n) insertion and O(log n) removal of the smallest item — far faster than repeatedly sorting a list.

Python 3.12 (WASM)
EditCopyAsk AIRun Code
import heapq

numbers = [5, 1, 8, 3, 9, 2]
heapq.heapify(numbers)          # rearranges the list in place into heap order

heapq.heappush(numbers, 0)       # add an item, maintaining heap order
smallest = heapq.heappop(numbers)  # remove and return the smallest item

print(smallest)   # 0
print(heapq.nsmallest(3, numbers))   # the 3 smallest items, sorted
print(heapq.nlargest(3, numbers))     # the 3 largest items, sorted

Use case: a task priority queue#

Python 3.12 (WASM)
EditCopyAsk AIRun Code
import heapq

tasks = []
heapq.heappush(tasks, (2, "Write report"))
heapq.heappush(tasks, (1, "Fix critical bug"))
heapq.heappush(tasks, (3, "Reply to emails"))

while tasks:
    priority, task = heapq.heappop(tasks)
    print(f"[{priority}] {task}")

# [1] Fix critical bug
# [2] Write report
# [3] Reply to emails

Heaps compare tuples element by element, so (priority, task) naturally sorts by priority first. For a max-heap (largest first), negate the priority values when pushing, since heapq only implements a min-heap directly.

8. bisect: Fast Operations on Sorted Lists#

bisect provides binary-search-based functions for finding insertion points and inserting into an already-sorted list in O(log n) time for the search (insertion itself is still O(n) for a list, due to shifting).

Python 3.12 (WASM)
EditCopyAsk AIRun Code
import bisect

scores = [10, 20, 30, 40, 50]

# Find where 35 would be inserted to keep the list sorted
position = bisect.bisect_left(scores, 35)
print(position)   # 3

bisect.insort(scores, 35)          # insert 35, keeping the list sorted
print(scores)                       # [10, 20, 30, 35, 40, 50]

Use case: grade lookup#

Python 3.12 (WASM)
EditCopyAsk AIRun Code
import bisect

def grade(score):
    breakpoints = [60, 70, 80, 90]
    grades = "FDCBA"
    index = bisect.bisect(breakpoints, score)
    return grades[index]

print(grade(55))   # F
print(grade(85))    # B
print(grade(95))     # A

This avoids a chain of if/elif comparisons and scales cleanly to more grade boundaries.

9. array: Compact, Typed Numeric Storage#

A regular Python list stores references to full objects, which has overhead for large collections of simple numbers. The array module stores raw numeric values in a compact, C-style layout, using much less memory for large numeric datasets.

Python 3.12 (WASM)
EditCopyAsk AIRun Code
from array import array

# 'i' = signed int type code; only that type is allowed in this array
numbers = array("i", [1, 2, 3, 4, 5])
numbers.append(6)

print(numbers)          # array('i', [1, 2, 3, 4, 5, 6])
print(numbers[0])        # 1
# numbers.append("x")     # TypeError — array enforces a single numeric type

For most everyday tasks, a list is simpler and flexible enough; reach for array specifically when memory efficiency for large, uniform numeric data matters, or when interfacing with lower-level code.

10. Choosing the Right Tool#

Notes#

• deque operations at both ends are O(1), but indexing into the middle of a deque (d[5]) is O(n) — unlike a list, it's not optimized for random access.
• Counter is itself a subclass of dict, so all standard dict methods also work on it.
• heapq operates on plain lists directly — there's no separate "Heap" object; the list itself is kept in heap order by the module's functions.
• bisect.insort still shifts elements in memory like any list insertion — the O(log n) benefit applies only to finding the position, not the insertion itself.
• Since regular dict preserves order as of Python 3.7, reach for OrderedDict specifically when you need its extra methods (move_to_end) or order-sensitive equality — not just for ordering alone.

Best Practices Checklist#

• Use deque instead of list for queue/stack patterns with frequent operations at the front
• Use Counter instead of manual dictionary counting logic
• Use defaultdict to eliminate repetitive "if key not in dict" existence checks
• Reach for ChainMap for layered configuration instead of manually merging dictionaries
• Use namedtuple (or typing.NamedTuple) for simple, immutable records instead of plain tuples with unclear positional meaning
• Use heapq instead of repeatedly sorting a list when you only need the smallest/largest item
• Use bisect for fast lookups and insertions into sorted lists instead of linear scans
• Reach for array only when memory efficiency for large numeric datasets genuinely matters — otherwise, a list is simpler