Skip to content
Open DegreeOpen Degree

Choose the right built-in data structure

I can choose between a list, a dict, a set and a tuple for a given task, and say what each one costs to look up, insert and iterate.

Domain
Python Programming
Level
foundation
Status
draft · v0.1.0
Also called
Lists and dictionaries, Python collections, dict vs list, Sets in Python
License
CC BY-SA 4.0

Learn first

Learn it

Scope

The four built-ins a Python program is mostly made of, and the reasons to reach for each. Choosing well is most of what separates code that stays fast from code that quietly does not.

In scope: list, dict, set and tuple; what each costs; mutability and what it means for arguments and keys. Out of scope: collections and the rest of the standard library, and formal complexity analysis, which have their own nodes.

What each one is for

  • List — an ordered sequence you will index, append to, and iterate. Finding a value in it means looking at the items one by one.
  • Dict — a mapping from keys to values, when you will look things up by something. The lookup does not get slower as the dictionary grows.
  • Set — membership and uniqueness, with the same fast lookup as a dict and no values.
  • Tuple — a fixed group of items, often of different meanings, that should not change. Being immutable, it can be a dict key.

The one decision that matters

Ask what the code does most often. If it asks “is this in there?” or “what is the value for this?”, a list is the wrong answer: every question walks the whole list, so the work grows with both the number of questions and the size of the data. A dict or set answers in about the same time regardless of size.

This is the single most common cause of a script that runs fine on a sample and takes hours on the real file. The Python wiki’s complexity table is the reference: list membership is O(n), dict and set membership is O(1) on average.

Mutability, arguments and keys

A list passed into a function is the same object the caller holds: mutating it changes their copy too, which is a feature when intended and a bug when not. A tuple cannot be changed, which is why it can be hashed and used as a dict key, and why it is the safer way to return a fixed group of values.

Common misconceptions

  • “A dict is a fancy list.” They answer different questions. A list is about order and position; a dict is about lookup by key.
  • “Sets are lists without duplicates.” Sets are unordered and their members must be hashable — a set of lists is not possible.
  • “Tuples are immutable, so a tuple is always safe as a key.” Only if everything inside it is hashable too. A tuple containing a list is not.
  • “Big collections need a library.” Most of the time the fix is the right built-in, not NumPy.

Notes for teachers

Give learners a script that checks membership against a list of 100,000 items, have them time it, then change one line to a set and time it again. The number does the teaching.

Then ask the better question: “what does this code ask most often?” — and have them answer it before choosing a structure, for three different tasks.

Resources

ResourceKindCostProvider
The Python Tutorial: data structuresreadingfreePython Software Foundation
Automate the Boring Stuff, chapter 4: listsreadingfreeAl Sweigart
Automate the Boring Stuff, chapter 5: dictionaries and structuring datareadingfreeAl Sweigart
Python wiki: time complexity of built-in operationsreferencefreePython Software Foundation

Courses that include it

draft

Python for a Coding Assessment

A refresher path through the Python graph for someone who has written Python before and has an assessment coming: run and read, rebuild the core, then work the way an assessment expects.

Prove it

Evidence of mastery

  • Given a task, picks a structure and justifies it by the operation the task does most often.
  • Replaces a repeated linear scan over a list with a dict or set lookup, and explains the difference it makes as the input grows.
  • Says which structures can be dictionary keys and why, without reciting a rule.
  • Predicts the output of code that mutates a list passed into a function, and says what a tuple would have changed.

Assessments that measure it

project

Python Take-Home Task

A timed take-home in the shape real hiring uses: read messy data, compute a result, test it, and hand over a repository someone else can run.

Credentials that include it

draft

Python Problem Solving

The holder can take an unfamiliar problem, write a tested Python solution someone else can run, and explain what it costs.

What learners show

Nothing to show yet. The publisher last published on 2026-09-20, and no aggregate for this outcome has reached the 50 learners a number needs. Open Degree does not track learners. About learner evidence.

What comes next