Dictionaries vs. Lists — I can choose dictionaries vs lists based on lookup by key vs position and justify the choice. - Computer Programming 1 Python

SECTION 1

Historical Context & Motivation

Programmers have always needed ways to organize collections of data. Early computer programs stored values in simple numbered slots called arrays, where each item was accessed by its numeric position — much like lockers in a hallway numbered 0, 1, 2, and so on. This approach worked well when you knew exactly which position held the data you wanted, but it became awkward when you wanted to look something up by a meaningful label, like a student's name or a product code.

As software grew more complex, computer scientists developed a second style of data storage — the associative array — which lets you pair a unique key (like a name) with a value (like a phone number). Python adopted both ideas: lists for ordered, position-based storage, and dictionaries for key-based lookup. Understanding the difference is one of the most important decisions you will make when designing a program.

1957 • Arrays in Fortran

Fortran, one of the first high-level languages, introduces arrays — ordered sequences of values accessed by integer index. This becomes the standard way to group data.

1969 • Associative Arrays in AWK

The Unix text-processing language AWK popularizes associative arrays, letting programmers use strings as keys instead of numbers. The idea of key→value lookup enters mainstream programming.

1991 • Python's First Release

Guido van Rossum releases Python 0.9.0, which includes both lists and dictionaries as built-in data types. Having both structures available from day one highlights Python's philosophy of offering the right tool for each job.

2017 • Ordered Dictionaries by Default

Starting with Python 3.7, dictionaries officially preserve insertion order. This blurs the boundary between lists and dicts, but their core purpose — position-based vs. key-based lookup — remains distinct.

The central question this lesson addresses is straightforward: When should you reach for a list, and when should you reach for a dictionary? The answer depends on whether you think about your data in terms of position ("give me the third item") or in terms of a meaningful label ("give me the item associated with 'Alice'").

SECTION 2

Core Principles & Definitions

Before you can choose between a list and a dictionary, you need a clear picture of what each one does and how it stores data internally. Both are collections — containers that hold multiple values — but they organize those values in fundamentally different ways.

List — Ordered by Position

A list stores items in a specific order. You access each item using its index — a number starting at 0. Example: fruits[2] gives you the third fruit. Lists are great when the order matters or when you want to loop through items one by one.

Dictionary — Organized by Key

A dictionary stores key-value pairs. You access each value using its unique key, often a string. Example: grades["Alice"] returns Alice's grade. Dictionaries shine when you need to look something up by a label.

Mutability

Both lists and dictionaries are mutable, meaning you can add, remove, or change items after creation. This flexibility makes them the two most commonly used data structures in Python.

Uniqueness of Keys

In a list, duplicate values are perfectly fine — you can have [5, 5, 5]. In a dictionary, each key must be unique. If you assign a new value to an existing key, the old value is overwritten.

✦

KEY TAKEAWAY

Think of a list like a numbered parking lot — you find your car by remembering "spot 14." Think of a dictionary like a contact list in your phone — you find a phone number by searching for the person's name, not by counting through every contact one by one.

SECTION 3

Visual Explanation — Lists vs. Dictionaries

The left side shows a list where each item is accessed by its numeric index (0, 1, 2). The right side shows a dictionary where each value is accessed by a meaningful key string. Notice the arrow (→) connecting each key to its value.

The diagram above captures the most important visual difference. In a list, you always say "give me item number n." In a dictionary, you say "give me the item labeled key." This distinction drives every design decision you will encounter when choosing between the two structures. If your data naturally has meaningful labels — like student names, product IDs, or country codes — a dictionary is usually the better choice. If your data is simply a sequence where order and position matter, a list is the way to go.

SECTION 4

How Lookup Works Under the Hood

Choosing between a list and a dictionary is not just about style — it also affects performance. Understanding why requires a peek at how Python actually finds data inside each structure.

List Lookup — Linear Search

When you access an element by index like fruits[2], Python jumps straight to position 2 in memory. That lookup is extremely fast — it takes the same amount of time no matter how long the list is. However, if you need to check whether a value exists (for example, "banana" in fruits), Python must scan through the list from the beginning until it finds a match or reaches the end. In the worst case, it checks every single element. Computer scientists describe this as O(n) time, where n is the number of items.

LIST MEMBERSHIP CHECK

Time ∝ n (worst case: check every element)

Where n is the number of items in the list. If the list has 1,000 items, Python may need up to 1,000 comparisons.

Dictionary Lookup — Hash Table

A dictionary uses a technique called hashing. When you write grades["Alice"], Python runs the key "Alice" through a hash function — a mathematical recipe that converts the key into a number. That number tells Python exactly where in memory the value is stored. This means the lookup takes roughly the same amount of time whether the dictionary has 10 entries or 10 million. Computer scientists call this O(1) or constant time.

DICTIONARY KEY LOOKUP

Time ≈ constant (regardless of dictionary size)

The hash function converts the key into a memory address in approximately one step. This is dramatically faster than scanning a list when n is large.

💡

Why Does This Matter?

Imagine you have a list of 100,000 student records and you need to find one student's grade. With a list, Python might check up to 100,000 entries. With a dictionary keyed by student name, Python finds the answer in essentially one step. For small data sets the difference is negligible, but for large ones it can mean the difference between a program that runs in milliseconds and one that takes minutes.

SECTION 5

When to Use Which — A Decision Flowchart

Choosing between a list and a dictionary comes down to a handful of questions about your data. The flowchart below walks you through the decision step by step. Ask yourself: does your data have natural labels? Do you need to look things up by name? Or is the order and position the most important thing?

Follow the diamond-shaped decision nodes to determine the best data structure. Start at the top: if your data has natural labels and you need fast lookup, choose a dictionary. If position and order matter most, choose a list.

Scenario	Best Choice	Why
A to-do list of tasks in order	`list`	Order matters; items are accessed by position (first task, next task).
Student grades looked up by name	`dict`	Each student name is a unique key; you look up by name, not by position.
High scores in a game (ranked)	`list`	Ranking is position-based: 1st place, 2nd place, etc.
Settings for an app (volume, theme, language)	`dict`	Each setting has a name (key) and a value; you look up by setting name.
Coordinates of points on a graph	`list`	Points are stored as ordered pairs; the sequence and index matter.

Common scenarios and the data structure they suggest

SECTION 6

Worked Example — Building a Contact Book

Let's walk through a realistic scenario. You are building a simple contact book app that stores names and phone numbers. You need to let the user look up any contact by name. We'll compare two approaches — one using a list and one using a dictionary — and justify which is better.

Contact Book: List vs. Dictionary

1
Step 1 — Identify the Data

We have three contacts: Alice (555-0101), Bob (555-0202), and Carol (555-0303). Each contact has a name and a phone number. We need to look up a phone number when given a name.
2
Step 2 — Attempt with a List

Using a list of lists: contacts = [["Alice", "555-0101"], ["Bob", "555-0202"], ["Carol", "555-0303"]]. To find Bob's number, we must loop through every sub-list and check if the first element equals "Bob". This requires a for loop:

for c in contacts: if c[0] == "Bob": print(c[1]) — This works but is O(n) for each lookup.
3
Step 3 — Attempt with a Dictionary

Using a dictionary: contacts = {"Alice": "555-0101", "Bob": "555-0202", "Carol": "555-0303"}. To find Bob's number, we simply write:

print(contacts["Bob"]) — One line, O(1) constant-time lookup. No loop needed.
4
Step 4 — Justify the Choice

The dictionary is the better choice here for three reasons: (1) each contact name is a unique, meaningful key; (2) we need fast lookup by name, not by position; and (3) the code is simpler and more readable.

Verdict: Use a dictionary. The data naturally maps names → numbers, which is exactly what dictionaries are designed for.
5
Step 5 — Adding and Updating

Adding a new contact is simple: contacts["Diana"] = "555-0404". Updating Bob's number: contacts["Bob"] = "555-9999". Both operations are O(1). With a list, adding is easy (append), but updating requires finding Bob first (O(n)).

Dictionaries make adding and updating by key just as efficient as looking up.

SECTION 7

Strengths & Limitations — Side by Side

Neither lists nor dictionaries are "better" in an absolute sense — each has strengths and weaknesses. The table below summarizes the key trade-offs you should consider when making your choice.

Feature	List	Dictionary
Access method	By integer index (position)	By key (string, number, tuple)
Order	Always ordered by position	Preserves insertion order (Python 3.7+)
Duplicates	Allowed — same value can appear multiple times	Keys must be unique; values can repeat
Lookup speed (by value/key)	O(n) — must scan the list	O(1) — hash-based, nearly instant
Memory usage	Less memory per element	More memory (stores keys + hash table)
Slicing	Supported (e.g., my_list[1:4])	Not supported directly
Best for	Sequences, ranked data, iteration	Labeled data, fast lookups, configuration

Comprehensive comparison of Python lists and dictionaries

✦

KEY TAKEAWAY

Lists trade memory efficiency for simplicity when data is naturally sequential. Dictionaries trade a bit more memory for blazing-fast key-based lookup. If you find yourself writing a loop to search a list for a specific value over and over, that's a strong signal you should be using a dictionary instead.

SECTION 8

Connection to Advanced Concepts

The list-vs-dictionary choice you are learning now is the foundation for more advanced data structure decisions you will encounter as you continue in computer science. Understanding this trade-off prepares you for topics like databases, caching, and algorithm design.

Concept You Know Now	Advanced Concept It Leads To
List (ordered sequence)	Arrays, linked lists, stacks, and queues — all position-based structures studied in Data Structures courses.
Dictionary (key→value mapping)	Hash maps, database indexes, caches (like Redis), and JSON data — all rely on key-based lookup.
O(n) vs. O(1) lookup	Big-O notation and algorithm analysis — the formal study of how code performance scales with input size.
Choosing the right structure	Software design and system architecture — selecting data structures is a core skill in professional development.

How today's concepts connect to future learning

Python also offers hybrid approaches. A list of dictionaries is extremely common — think of a spreadsheet where each row is a dictionary with column names as keys, and the rows are stored in a list. For example: students = [{"name": "Alice", "grade": 92}, {"name": "Bob", "grade": 85}]. This pattern combines the ordered nature of lists with the labeled access of dictionaries. You will see it everywhere in web development, data science, and API design.

ℹ

Looking Ahead

In AP Computer Science and college-level courses, you will learn about trees, graphs, and heaps — more specialized data structures that solve problems neither lists nor dictionaries handle well. The skill of justifying your data structure choice is transferable to every one of those future topics.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain in your own words the fundamental difference between how a list and a dictionary store and retrieve data. Use the terms index and key in your answer.

Show answer

A list stores items in a specific order and retrieves them using an integer index — the item's position, starting from 0. A dictionary stores items as key-value pairs and retrieves them using a unique key, which is typically a string or number that carries meaning (like a name or ID). The key difference is that list access is position-based ("give me item #3") while dictionary access is label-based ("give me the item called 'Alice'"). This means lists are ideal when order matters, and dictionaries are ideal when you need to look something up by a meaningful identifier.

Question 2: BASIC CALCULATION

You have a list of 500 student names and need to check if "Zara" is in the list. In the worst case, how many comparisons does Python make? If you stored the same data in a dictionary (with names as keys), approximately how many operations would the lookup take? Which structure is better for this task?

Show answer

With a list, Python performs a linear search. In the worst case ("Zara" is not in the list or is at the very end), Python makes 500 comparisons — one for each element. This is O(n) where n = 500. With a dictionary, the hash function converts the key "Zara" into a memory address in approximately 1 operation (constant time, or O(1)), regardless of how many entries exist. The dictionary is clearly better for this task because it avoids scanning through hundreds of elements. Even though both approaches work, the dictionary scales far better as the data set grows.

Question 3: INTERMEDIATE

You are building a program to track inventory for a small store. Each product has a name, a price, and a quantity in stock. You need to: (a) look up a product's price by its name, and (b) list all products in the order they were added. Would you use a list, a dictionary, or a combination? Write the Python code to create the data structure and look up the price of "Notebook".

Show answer

A dictionary is the best primary structure because you need to look up products by name (key-based access). Since Python 3.7+, dictionaries preserve insertion order, so requirement (b) is also satisfied. You could write:

inventory = {"Pen": {"price": 1.50, "qty": 200}, "Notebook": {"price": 4.99, "qty": 75}, "Eraser": {"price": 0.99, "qty": 150}}

. To look up the price: print(inventory["Notebook"]["price"]) which outputs 4.99. This is a nested dictionary — the outer keys are product names, and each value is itself a dictionary holding price and quantity. This design gives O(1) lookup by product name and preserves the order products were added.

Question 4: APPLIED

A teacher asks you to write a program that counts how many times each word appears in a paragraph of text. She gives you the paragraph as a single string. Would you store the word counts in a list or a dictionary? Justify your answer, then write the Python code that builds the word-count structure from the string text = "the cat sat on the mat the cat".

Show answer

A dictionary is the correct choice because each word is a natural key and its count is the value. You need to look up whether a word has already been seen (key-based lookup) and update its count. Using a list would require searching through the entire list for each word, making the program much slower. Here is the code:

text = "the cat sat on the mat the cat"
word_counts = {}
for word in text.split():
    if word in word_counts:
        word_counts[word] += 1
    else:
        word_counts[word] = 1
print(word_counts)

. The output is {"the": 3, "cat": 2, "sat": 1, "on": 1, "mat": 1}. The in operator on a dictionary is O(1), making this efficient even for very large texts.

Question 5: CRITICAL THINKING

Consider a music playlist app. The app needs to: (1) keep songs in playback order, (2) let users skip to a song by title, (3) allow duplicate song titles (e.g., "Remix" could appear twice). Could you use only a list? Only a dictionary? Or do you need both? Design a data structure solution and explain the trade-offs of your approach.

Show answer

This problem requires careful analysis because the three requirements pull in different directions. Requirement (1) favors a list — it preserves order naturally. Requirement (2) favors a dictionary — it allows fast title-based lookup. Requirement (3) disqualifies a pure dictionary because dictionary keys must be unique, and duplicate song titles would overwrite each other. A good solution uses both: store the playlist as a list of dictionaries, like

playlist = [{"title": "Remix", "artist": "DJ A"}, {"title": "Hello", "artist": "Adele"}, {"title": "Remix", "artist": "DJ B"}]

. Playback order is maintained by the list. To find songs by title, you would loop through the list (O(n)), or you could build a secondary dictionary mapping titles to a list of indices for faster lookup: title_index = {"Remix": [0, 2], "Hello": [1]}. The trade-off is extra memory and complexity, but it satisfies all three requirements. This illustrates that real-world problems often benefit from combining data structures rather than choosing just one.

SUMMARY

Lesson Summary

Summary

Python's two most versatile data structures — lists and dictionaries — serve fundamentally different purposes. A list stores items in a specific order and retrieves them by integer index (position), making it ideal for sequences, ranked data, and iteration. A dictionary stores key-value pairs and retrieves values by meaningful key, making it ideal for labeled data, configurations, and any scenario where you need to look something up by name.

Performance matters: checking whether a value exists in a list is O(n) — linear time, while looking up a key in a dictionary is O(1) — constant time thanks to hash functions. The decision rule is clear: ask yourself "Will I look this data up by position or by a label?" If the answer is position, use a list. If the answer is label, use a dictionary. Many real-world programs combine both — such as a list of dictionaries — to get the best of both worlds.