Python Data Structures: Lists, Dicts, Sets, and Tuples

Scenario context

Python's four built-in collections are not interchangeable — their internals are fundamentally different. list is a dynamic array: fast at the end, slow for membership. dict is a hash table: O(1) key lookup, insertion-order-preserving since Python 3.7. set is a hash set: O(1) membership, no duplicates, unordered. tuple is immutable and hashable: safe as a dict key, cheaper to create than a list. Pick the rig…

This walkthrough focuses on The O(n) Bug That Turned a 30-Minute Batch Job into an Overnight Disaster.

Before making a design choice, clarify:

• David works on a data pipeline that processes customer transactions at a fintech startup.
• Every night, the pipeline loads one million already-processed transaction IDs from a database, then iterates over each incoming event to check whether its ID is already in that loaded collection — a "have we processed t…
• David's code looked completely reasonable.

Concepts in play: database-indexing, python-concurrency-nogil, hash-tables-and-bloom-filters, stack-and-queue-data-structures

Stage 1 — Python's Four Core Collections at a Glance

• Before going deeper, here is the single most important reference table for choosing a collection.
• Every row describes a behavioral guarantee — not a style preference.
• A few entries deserve immediate clarification.
• Ordered for dict : Since Python 3.7, dictionaries preserve insertion order as a language guarantee.

Observable outcome: Ordered for dict : Since Python 3.7, dictionaries preserve insertion order as a language guarantee.

Stage 2 — Under the Hood: How Lists, Dicts, Sets, and Tuples Actually Work

• Lists: A Resizable Array With Amortized O(1) Append Python's list is a dynamic array — a contiguous block of memory holding object references (pointers to Python objects).
• When you create a list, Python allocates an initial capacity.
• As you append items, Python fills those pre-allocated slots.
• When capacity runs out, Python allocates a new, larger block (typically 1.125× to 2× the current capacity), copies all existing references, and frees the old block.

import sys

lst = []
for i in range(8):
    lst.append(i)
    print(f"len={len(lst)}, bytes={sys.getsizeof(lst)}")

# len=1, bytes=88    (pre-allocated a few slots)
# len=2, bytes=96
# len=3, bytes=104
# len=4, bytes=104   (all pre-allocated slots used)
# len=5, bytes=120   (resize triggered)
# len=6, bytes=120
# len=7, bytes=120
# len=8, bytes=120

config = {
    "host": "localhost",
    "port": 5432,
    "database": "myapp",
}

# O(1) lookup — Python hashes "port" and jumps directly to its slot
print(config["port"])    # 5432

# Only hashable types can be dict keys
valid_key = (1, 2, 3)
config[valid_key] = "tuple key works"   # OK — tuples are hashable

bad_key = [1, 2, 3]
# config[bad_key] = "fails"             # TypeError: unhashable type: 'list'

Observable outcome: When capacity runs out, Python allocates a new, larger block (typically 1.125× to 2× the current capacity), copies all existing references, and frees the old block.

Stage 3 — How Python's dict and set Actually Work Inside CPython

• The Internals of Python Dict Before Python 3.6, CPython's dict was a standard open-addressing hash table with no ordering.
• Python 3.6 introduced a compact hash table design that CPython uses today, and Python 3.7 enshrined insertion-order preservation as a language guarantee.
• The compact design uses two separate data structures: - An indices array — a compact array that maps hash slot positions to integer offsets into the entries array - An entries array — stores (hash, key, value) triples i…
• Calls hash("name") and truncates to the current table size to get slot s 2.

Observable outcome: Calls hash("name") and truncates to the current table size to get slot s 2.

Stage 4 — Choosing the Right Collection: A Decision Flowchart

• The questions in this flowchart are ordered to eliminate wrong options as fast as possible.
• Starting from the top, each question cuts the candidate pool in half.
• The leaf node tells you exactly which collection to use and why.
• Reading the flowchart: if you need fast in checks or key lookups, you immediately route to the hash-based types — dict , set , or frozenset .

graph TD
    A[Start: Pick a Collection] --> B{Need fast membership test or key lookup?}
    B -->|Yes| C{Need to associate a value with each key?}
    B -->|No| D{Need to preserve insertion order?}
    C -->|Yes| E[Use dict]
    C -->|No| F{Does the collection itself need to be hashable?}
    F -->|Yes| G[Use frozenset]
    F -->|No| H[Use set]
    D -->|Yes| I{Will the collection change after creation?}
    D -->|No| J[Consider set for automatic dedup]
    I -->|Yes| K[Use list]
    I -->|No| L[Use tuple]

Observable outcome: Reading the flowchart: if you need fast in checks or key lookups, you immediately route to the hash-based types — dict , set , or frozenset .

Stage 5 — Four Real-World Patterns Using Python Collections in Production

• These patterns cover the most common production scenarios.
• Each one shows why a specific collection is the right tool — not just by convention, but because of its internal behavior.
• Pattern 1 — LRU Cache Backed by dict A Least-Recently-Used cache needs O(1) key lookup and O(1) eviction.
• collections.OrderedDict adds the move to end() method needed to track usage order.

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()   # insertion order = access order

    def get(self, key: str):
        if key not in self.cache:
            return None
        self.cache.move_to_end(key)   # promote to most-recently-used
        return self.cache[key]

    def put(self, key: str, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)  # evict the least-recently-used

cache = LRUCache(3)
cache.put("a", 1)
cache.put("b", 2)
cache.put("c", 3)
cache.get("a")           # promotes "a"
cache.put("d", 4)        # evicts "b" (least recently used)
print(list(cache.cache.keys()))   # ['c', 'a', 'd']

def deduplicate_events(raw_events: list) -> list:
    """Remove duplicate events by id, preserving first-occurrence order."""
    seen_ids = set()
    unique = []
    for event in raw_events:
        if event["id"] not in seen_ids:   # O(1)
            seen_ids.add(event["id"])
            unique.append(event)
    return unique

events = [
    {"id": "evt_001", "amount": 99.99},
    {"id": "evt_002", "amount": 14.99},
    {"id": "evt_001", "amount": 99.99},   # duplicate webhook retry
    {"id": "evt_003", "amount": 49.99},
]
clean = deduplicate_events(events)
print(len(clean))   # 3 — one duplicate removed

Observable outcome: collections.OrderedDict adds the move to end() method needed to track usage order.

Stage 6 — Matching Use Case to Collection: A Quick Reference

• Use this table as a decision checklist when you are about to introduce a new collection variable.
• Match the row that best describes your access pattern and start from the "Best Collection" column.

Observable outcome: Match the row that best describes your access pattern and start from the "Best Collection" column.

End-to-end outcome

After working through the stages, you should be able to explain:

• Every one of these lessons was paid for by a real production incident or a code review that went on far longer than it needed to.
• • The O(n) membership trap is subtle.

Alternatives considered

list vs deque for Queue Workloads

Using a list as a FIFO queue — appending to the right and removing from the left with pop(0) — is one of the most common accidental O(n) patterns in Python.

dict vs defaultdict vs Counter

Plain dict requires explicit handling of missing keys, leading to repetitive if key not in d guards.

set vs frozenset

set is mutable and unhashable — it cannot be used as a dict key or placed inside another set.

Failure and degraded modes

The source does not isolate a separate failure mode. Limits that matter for the scenario are called out in the stage decisions above.