Module 4 - Data Structures (Pythonic)

Reading time: ~10 minutes | Level: Foundation → Engineering

Here is a question before you start.

# Which of these is faster for 10 million items?

items_list = list(range(10_000_000))
items_set  = set(range(10_000_000))

9_999_999 in items_list   # Option A
9_999_999 in items_set    # Option B

Option B is not "a little faster."

On a modern machine, Option A takes roughly 1 second. Option B takes under 1 microsecond.

That is a difference of one million times.

Same data. Same Python. Different structure. Radically different outcome.

This is what this module is about: understanding why structures behave the way they do, so you can build systems that survive at scale.

What You Will Master

• The internal architecture of lists, tuples, dicts, and sets - not just "how to use them" but how CPython implements them
• Why dict lookup is O(1) and how hash collisions are resolved
• When a list becomes your worst enemy and a set becomes your best friend
• Memory diagrams for shallow copy vs deep copy - and why confusing them causes production bugs
• Python's Timsort algorithm and how to exploit it with key functions
• heapq for priority queues - the backbone of task schedulers and ML systems
• collections.deque for O(1) double-ended access
• Counter and defaultdict for analytics and grouping patterns
• A complete decision framework: given a workload, which structure is correct?
• Real connections to NumPy, pandas, PyTorch, and scikit-learn

Prerequisites

You should be comfortable with:

• Python basic syntax (variables, loops, functions)
• Understanding that Python has types (int, str, list)
• Module 3 (Core Python Syntax) - especially the name binding model

Why Data Structures Are Not Optional Knowledge

Most engineers learn data structures as syntax:

• "Use a list when you need an ordered collection."
• "Use a dict for key-value pairs."
• "Sets remove duplicates."

That knowledge gets you to working code. It does not get you to scalable systems.

Consider a real scenario from a production ML pipeline:

# Deduplication step - runs on 50 million records daily

# Engineer A wrote this:
seen = []
unique_records = []
for record in records:
    if record["id"] not in seen:   # O(n) membership check
        seen.append(record["id"])
        unique_records.append(record)

# Engineer B wrote this:
seen = set()
unique_records = []
for record in records:
    if record["id"] not in seen:   # O(1) membership check
        seen.add(record["id"])
        unique_records.append(record)

Engineer A's code: O(n²) - 50 million records becomes 2.5 trillion operations. Pipeline timeouts.

Engineer B's code: O(n) - 50 million operations. Pipeline completes in minutes.

Same logic. Same output. One is unusable in production.

:::warning The Hidden Quadratic Trap The most common performance disaster in Python code is using a list where a set belongs. It works perfectly in tests with 100 records. It destroys systems at 1 million. :::

The Mental Framework: Data Structures as Access Contracts

Every data structure is a contract about what operations are cheap and what are expensive.

Structure	Cheap operations	Expensive operations
list	a[i], append, iteration	search, insert at front, delete from middle
dict	key lookup, insert, delete, membership	iteration in value order, sorting by value
set	membership, add, remove, union, intersection	indexing (impossible), ordering (impossible)
tuple	t[i], unpack, hashing	mutation (impossible)
heap	min retrieval, insert	search, arbitrary access

When you internalize these contracts, choosing the right structure becomes automatic.

Module Overview - What You Will Study

Lesson 01 - Lists: Dynamic Arrays Under the Hood

You will understand how CPython implements lists as dynamic arrays in C, what over-allocation means, why append() is amortized O(1) but insert(0, x) is O(n), and what memory layout looks like when you store references instead of values.

Lesson 02 - Tuples and Immutability

You will understand why tuples use less memory than lists, how CPython caches small tuples, what namedtuples give you for free, and precisely when to choose a tuple over a list - including why tuples can be dictionary keys and lists cannot.

Lesson 03 - Dictionary Hashing Mechanism

You will understand what happens inside CPython when you do d["key"], how hash tables work, what open addressing means, how Python manages the load factor, and why insertion order is preserved since Python 3.7.

Lesson 04 - Sets and Mathematical Operations

You will understand how sets are hash tables without values, why item in my_set is O(1), how union/intersection/difference are implemented, what frozenset is for, and when to replace a list with a set.

Lesson 05 - Comprehensions Deep Dive

You will understand why list comprehensions are faster than explicit loops, what generator expressions are and when to use them instead, how nested comprehensions work, and when NOT to use comprehensions (readability matters).

Lesson 06 - Shallow vs Deep Copy

You will understand the difference between assignment (aliasing), copy.copy() (shallow), and copy.deepcopy() (deep), with full memory diagrams, performance benchmarks, and the exact bugs each choice causes in data pipelines.

Lesson 07 - Mutable vs Immutable Revisited

You will understand hashability, why dict keys must be immutable, frozen dataclasses, and the concurrency implications of mutability in shared state systems.

Lesson 08 - Memory References and Aliasing

You will understand object graphs, how aliasing causes silent bugs in data pipelines, reference counting and garbage collection, and how to debug aliasing issues systematically.

Lesson 09 - Time Complexity of Data Structures

You will understand Big-O notation for all Python structures, amortized analysis, average-case vs worst-case, and the engineering habit of asking "what happens when this scales 1000x?".

Lesson 10 - Sorting Mechanisms

You will understand Python's Timsort algorithm, why it is stable and adaptive, the difference between sorted() and .sort(), and when sorting inside a loop destroys performance.

Lesson 11 - Custom Sorting with Key

You will understand key= functions, operator.itemgetter and attrgetter, multi-criteria sorting with tuple keys, functools.cmp_to_key(), and how to build production-grade ranking systems.

Lesson 12 - Heap and Priority Queue

You will understand min-heaps, the heapq module, heappush, heappop, heapify, nlargest, nsmallest, and how priority queues power ML inference schedulers and task systems.

Lesson 13 - Deque and Collections

You will understand collections.deque for O(1) operations at both ends, rotating, bounded buffers with maxlen, and when deque outperforms list - with sliding window algorithm examples.

Lesson 14 - Counter and Defaultdict

You will understand Counter for word frequency and analytics, multiset arithmetic, most_common(), and defaultdict for grouping patterns and graph adjacency lists - without KeyError bugs.

Lesson 15 - Data Structure Selection Strategy

You will build a decision framework: given a problem's access patterns, mutation needs, and scale requirements, choose the correct Python structure. This is the capstone that ties everything together.

Projects in This Module

After the lessons, you will apply everything to three real engineering projects:

Project 1 - Inventory Management Tool Build a CLI inventory system using dict, defaultdict, Counter, and set - with O(1) lookups, category grouping, low-stock alerts, and sales analytics.

Project 2 - Frequency Analyzer Build a text frequency analyzer using Counter, defaultdict, heapq, and deque - including streaming analytics and sliding window frequency tracking.

Project 3 - Priority Task Scheduler Build a priority-based task scheduler using heapq - with delayed execution, retry logic, and worker simulation.

AI/ML Connection - Why This Module Matters for Machine Learning

Data structures are not abstract concepts when you work in AI.

NumPy arrays are implemented as contiguous memory blocks - the same principle as Python lists, but without Python object overhead. Understanding list internals helps you understand why NumPy is 100x faster for numerical computation.

pandas DataFrames use dictionaries internally to map column names to arrays. Every df["column"] is a dictionary lookup. Understanding hash tables makes pandas behavior predictable.

PyTorch DataLoaders use deque-based batch queues internally. Understanding deque mechanics helps you understand batch processing behavior.

Feature stores (Feast, Tecton) use hash-based lookup tables - the same principle as Python dicts - to retrieve features at O(1) per entity.

scikit-learn's LabelEncoder maintains a dictionary mapping class labels to integers. Understanding dict internals helps you understand why encoding is fast even for large label spaces.

Every concept in this module appears in production ML infrastructure.

How to Study This Module

1. Do not skip lessons. Each lesson builds on the previous one. Memory references (Lesson 08) make no sense without name binding from Module 3. Selection strategy (Lesson 15) is meaningless without knowing the complexity of each structure.

2. Run every code example. Reading code is not enough. Type it, run it, modify it.

3. Measure performance. Use time.time(), timeit, and sys.getsizeof(). See the difference with your own eyes.

4. Draw memory diagrams. When a concept involves references, draw boxes and arrows. This forces understanding rather than memorization.

5. Think in scale. For every code example, ask: what happens with 10 million records instead of 10?

Key Takeaways - Module Mindset

• Data structures are performance contracts, not just storage containers
• The same logic with a different structure can be O(n) or O(n²) - the difference is system survival
• Python's built-in structures are implemented in C and are extremely well-optimized - learn to use them correctly
• Every structure trades something: memory for speed, flexibility for safety, mutability for hashability
• The engineering habit is to ask "what is the access pattern?" before writing a single line of code

:::tip Engineering Maturity Test After completing this module, you should be able to answer: "Given a system that needs to check user permissions 500,000 times per second against a list of 2 million authorized users, which data structure do you use and why?" - in under 5 seconds. :::