Why This Matters
Task: Find a book in a library.
Approach 1: Books piled randomly on floor
Time: Hours (check every book)
Approach 2: Books organized by author, on labeled shelves
Time: Minutes (go directly to right shelf)
Same data (books), different organization → 1000× speed difference.
This is data structures: How you organize data determines what operations are fast vs. slow.
What You’ll Learn
- Why organization matters (operation performance)
- Four fundamental structures (list, dict, set, tuple)
- Trade-offs (memory vs. speed, flexibility vs. efficiency)
- When each structure is the right choice
Lists: Ordered Sequences
What It Is
Ordered collection where position matters.
scores = [85, 92, 78, 95, 88]
# 0 1 2 3 4 (indices)
Fast Operations
# Access by index: O(1) - constant time
first = scores[0] # Fast
third = scores[2] # Fast
# Append to end: O(1)
scores.append(90) # Fast
Slow Operations
# Search for value: O(n) - linear time
if 78 in scores: # Must check each element
print("Found!")
# Insert at beginning: O(n)
scores.insert(0, 100) # Must shift all others
When to Use
- Need to maintain order
- Access by position frequently
- Iterate through all elements
- Append to end often
Example: Log entries, time series data, processing queue.
Dictionaries: Key-Value Lookup
What It Is
Mapping from keys to values. Fast lookup by key.
student_grades = {
'Alice': 92,
'Bob': 85,
'Charlie': 95
}
Fast Operations
# Lookup by key: O(1) - constant time (average)
grade = student_grades['Alice'] # Fast!
# Add/update: O(1)
student_grades['David'] = 88 # Fast
# Check existence: O(1)
if 'Alice' in student_grades: # Fast
print("Found!")
Slow Operations
# Find key by value: O(n)
# No direct reverse lookup
for name, grade in student_grades.items():
if grade == 92:
print(f"Found: {name}") # Must check all
When to Use
- Need fast lookup by identifier
- Data naturally has key-value structure
- Keys are unique
Example: User profiles (user_id → data), configuration settings, caches.
Sets: Unique Elements, No Order
What It Is
Collection of unique items, no duplicates, no order.
visited_pages = {'home', 'about', 'contact'}
Fast Operations
# Check membership: O(1)
if 'home' in visited_pages: # Fast
print("Already visited")
# Add element: O(1)
visited_pages.add('products') # Fast
# Remove duplicates: O(n)
numbers = [1, 2, 2, 3, 3, 3, 4]
unique = set(numbers) # {1, 2, 3, 4} - Fast!
Set Operations
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
# Union: Elements in either
A | B # {1, 2, 3, 4, 5, 6}
# Intersection: Elements in both
A & B # {3, 4}
# Difference: Elements in A but not B
A - B # {1, 2}
When to Use
- Need uniqueness guarantee
- Fast membership testing critical
- Set operations (union, intersection)
- Order doesn’t matter
Example: Unique visitor IDs, tags, category memberships.
Tuples: Immutable Sequences
What It Is
Like list, but can’t be modified after creation.
point = (3, 5) # x, y coordinates
rgb_color = (255, 128, 0) # red, green, blue
Why Use Immutable?
# Can use as dictionary key (lists can't!)
locations = {}
locations[(3, 5)] = 'treasure' # Tuple as key ✓
# locations[[3, 5]] = 'treasure' # List as key ✗ ERROR
# Guarantee no modification
def process(data: tuple):
# Caller knows data won't be changed
pass
When to Use
- Data shouldn’t change (coordinates, RGB colors, dates)
- Need to use as dict key
- Want to signal “don’t modify this”
Example: Function returns (status, result), database row, coordinates.
Choosing the Right Structure: Decision Tree
Do you need key-value lookup?
├─ YES → Dictionary
└─ NO
├─ Need fast membership testing + uniqueness?
│ └─ YES → Set
└─ NO (need ordered sequence)
├─ Will it change after creation?
│ ├─ YES → List
│ └─ NO → Tuple
Real-World Example: Word Frequency Counter
Naive Approach: List of Lists
word_counts = []
def count_word(word):
"""Slow: O(n) to find word"""
for item in word_counts:
if item[0] == word:
item[1] += 1
return
word_counts.append([word, 1])
# Process document
for word in document:
count_word(word) # Gets slower with each unique word!
Problem: Must scan entire list to find word. O(n²) total time.
Better: Dictionary
word_counts = {}
def count_word(word):
"""Fast: O(1) lookup and update"""
word_counts[word] = word_counts.get(word, 0) + 1
# Process document
for word in document:
count_word(word) # Constant time per word! O(n) total
1000× faster for large documents.
Memory vs. Speed Trade-Offs
Dictionary: Fast Lookup, More Memory
# Stores ~3× more memory than list
# But lookups are O(1) vs O(n)
When to pay memory cost: Lookups frequent, data size moderate.
List: Less Memory, Slower Search
# Minimal memory overhead
# But search is O(n)
When acceptable: Small collections, rare searches, need order.
Set: Fast Membership, No Duplicates
# Similar memory to dict
# Enforces uniqueness (may be desired or unwanted)
When to use: Need uniqueness + fast membership test.
Cross-Domain Connections
Algorithms: Operation Complexity
From CODE-300.1: Algorithm Analysis:
Structure choice determines algorithm performance:
– List search: O(n)
– Dict lookup: O(1)
– Sorted list search: O(log n) with binary search
Databases: Index Structures
From DATA-100.2: Data Modeling:
Database indices are like dictionaries:
– Without index: Scan all rows (O(n))
– With index: Direct lookup (O(log n))
Machine Learning: Feature Storage
From ML-200.3: Feature Engineering:
# Store user features
user_features = {
'user123': [age, income, clicks, ...], # Dict of lists
'user456': [...]
}
Pattern Passport
Pattern Observed: REPRESENTATION TRADE-OFF
How It Appears Here:
– Structure = How data is organized
– Operations = Actions performed on data
– Trade-offs = Fast operations vs. memory vs. constraints
Representation:
– List: [a, b, c] — ordered, indexed
– Dict: {key: value} — mapped pairs
– Set: {a, b, c} — unique, unordered
– Tuple: (a, b, c) — immutable sequence
Transformation Rules:
– List ↔ Set: Remove/allow duplicates
– Dict → List: Extract keys or values
– Any → Tuple: Make immutable
Assumptions:
– Data fits in memory
– Operation frequency justifies structure choice
– Correctness maintained across representations
Failure Conditions:
1. Wrong structure: Slow operations become bottleneck
2. Memory overflow: Dict/set use too much memory
3. Mutability issues: Modifying when immutability expected
4. Type constraints: Using list as dict key (not hashable)
Related Disciplines:
– Algorithms CODE-300.1: Complexity analysis
– Data DATA-100.2: Database indexing
– ML ML-200.3: Feature representation
Next Learning Steps:
1. CODE-200.1: Algorithm Complexity — Understanding O(n) notation
2. CODE-300.1: Advanced Data Structures — Trees, heaps, graphs
3. CODE-300.2: Algorithm Design — Choosing algorithms and structures
Summary: Organization Determines Performance
Data structure choice = performance trade-off.
Three key insights:
- Organization matters: Same data, different structure → different performance
- No perfect structure: Each optimizes some operations, sacrifices others
- Choose based on use: What operations are frequent? What constraints matter?
When to use what:
– List: Ordered sequence, frequent iteration
– Dict: Fast key-based lookup
– Set: Uniqueness + fast membership testing
– Tuple: Immutable ordered data
Common mistakes:
– Using list when dict would be 1000× faster
– Using dict when tuple would be clearer (and hashable)
– Not considering memory costs for large datasets
The value: Right structure makes code fast, clear, and correct. Wrong structure causes performance disasters.
Exercises
-
Benchmark: Create list and dict with 10,000 items. Time 1000 lookups. Compare.
-
Refactor: Given list of (name, score) tuples, rewrite using dict. Show performance difference.
-
Unique users: You have 1M user IDs (with duplicates). Find unique count. Which structure?
-
Read-heavy vs write-heavy: When would list beat dict despite slower lookup?
Revision History
2026-07-30: Substantially revised with performance examples, trade-off analysis, cross-domain connections.
2024-06-01: Originally published.
Reproducible Code
Available at:
– Code/data_structure_examples.py
– validation/test_data_structures.py
cd Categories/03-Code/100.2-Data-Structures
python validation/test_data_structures.py