Python Data Structures

Overview

Python's built-in collection types, list, tuple, dict, and set, look interchangeable at a glance but have genuinely different performance characteristics driven by how they're implemented internally. Lists and tuples are ordered sequences backed by contiguous arrays; dicts and sets are hash tables. That implementation difference is what makes membership checks and key lookups fast on a dict/set and slow on a list/tuple, and it's the single most common hidden performance bug in Python code, using a list where a set or dict would make an O(n) operation O(1).

Quick Reference

Syntax

users = ["alice", "bob", "carol"]           # list
point = (3.0, 4.0)                            # tuple
config = {"debug": True, "workers": 4}         # dict
seen_ids = {101, 102, 103}                     # set

Examples

# Slow: O(n) membership check against a growing list, repeated
# for every item - O(n * m) overall for m checks.
allowed = ["free", "pro", "enterprise"]
if plan in allowed:  # fine for 3 items, a real cost at scale
    ...

# Fast: O(1) average membership check against a set
allowed = {"free", "pro", "enterprise"}
if plan in allowed:
    ...

Visual Diagram

Common Mistakes

• Using a list for repeated membership checks (in) when a set would turn an O(n) scan into an O(1) average-case lookup.
• Trying to use a list as a dictionary key or set member and being surprised by the TypeError: unhashable type, reach for a tuple instead if the collection is fixed-size.
• Using a list where insertion order genuinely doesn't matter and only uniqueness/fast lookup does, a set communicates that intent and performs better.
• Mutating a list while iterating over it directly, which silently skips or duplicates elements because the indices shift underneath the iteration.

Performance

• Membership checks: O(1) average for set/dict, O(n) for list/tuple; this is the single highest-leverage data-structure choice in typical Python code.
• Appending to the end of a list is amortized O(1); inserting at the beginning (list.insert(0, x)) is O(n) because every subsequent element has to shift, a collections.deque is the right structure for frequent front-insertion.
• Dict and set operations degrade toward O(n) worst case under pathological hash collisions, but Python's hash implementation makes this a non-issue for typical real-world keys.

Best Practices

• Default to a set for any collection whose primary use is membership testing or deduplication, not a list.
• Use tuples for fixed-size, heterogeneous data (coordinates, database rows) and lists for variable-length, homogeneous collections.
• Reach for collections.deque instead of a list when a collection needs fast insertion/removal at both ends, not just the end.
• Profile before assuming a data-structure change matters for a specific hot path; the complexity difference is real, but it only shows up meaningfully at real scale.