Both lists and dictionaries are collections of data. You can use them to store and retrieve data later. Lists are ordered collections of elements indexed by numeric position. Dictionaries are unordered collections of values indexed by arbitrary keys. Since they are different, they have different performance implications.
names = ["Alice", "Asia", "Aaron", "Adarsh", "Avril"] print(names[3]) # Output: "Adarsh"
If we have a list of strings that represent names, we can access a particular element by its index. When we know the exact position of the element we want, accessing it is very fast. The time it takes to access an element in a list is constant, no matter how many elements are in the list.
names = ["Alice", "Asia", "Aaron", "Adarsh", "Avril"]
# Slow
for name in names:
if name == "Adarsh":
print("Found Adarsh!")
However, if we want to determine whether a particular string is in the list, we must walk through each element. If there are 10 strings, this will not take long, even if the string is at the end. But what if there are many, many strings, like in the University’s directory? Finding a string in a list will take longer when there are more elements. The time it takes to find an element in a list is linear, meaning it grows with the number of elements in the list. And if the element is not in the list, we must check every element to be sure.
grades = {
"Alice": 85,
"Asia": 90,
"Aaron": 80,
"Adarsh": 100,
"Avril": 95
}
# Fast
print(grades["Adarsh"]) # Output: 100
If you use a dictionary to store names (perhaps mapped to their address or grade), then you can look up keys instantly. On average, dictionaries’ lookup does not take longer no matter how many elements there are. This is a slight simplification, but dictionaries are designed to be fast for looking up values. The time it takes to look up a value in a dictionary is constant, no matter how many elements are in the dictionary, similar to how it is for lists. This is actually an incredible fact, and future Computer Science courses will explain how this is possible. For now, just remember that dictionaries are great for looking up keys quickly.
grades = {
"Alice": 85,
"Asia": 90,
"Aaron": 80,
"Adarsh": 100,
"Avril": 95
}
# Slow
for name, grade in grades.items():
if grade == 100:
print(name, "has a grade of 100")
However, if we want to determine whether a particular value is in the dictionary, we must walk through each key/value pair. As it was with the list, if there are 10 key/value pairs, this will not take long. But again, what if there are many, many key/value pairs? Finding a value in a dictionary will take longer when there are more key/value pairs. In the worst possible situation, we must check every key/value pair to be sure. The time it takes to find a value in a dictionary is linear, meaning it grows with the number of key/value pairs in the dictionary.
grades = {
100: "Adarsh",
95: "Avril",
90: "Asia",
85: "Alice",
80: "Aaron"
}
# Fast
print(grades[100]) # Output: "Adarsh"
If you were certain that every student had a unique grade, you could invert the dictionary. This would allow you to look up a student by their grade, which would be very fast. This is a common strategy when you need to look up values in a dictionary, perhaps having both a dictionary and its inverse dictionary. However, this only works if each student had a unique grade. Dictionary keys must be unique, but values do not have to be.
student_grades = {
100: ["Ada", "Adarsh", "Axel"],
95: ["Avril", "Asia"],
90: ["Alice"],
85: [],
80: ["Aaron"]
}
students = student_grades[100]
for student in students:
if student == "Adarsh":
print("Adarsh had a 100!")
Dictionaries can contain lists, and lists can contain dictionaries. This allows you to organize your data in many different ways. We previously saw how we could group related data together using lists inside of dictionaries. This can have interesting performance implications, if we are able to organize our data effectively.
In the example shown here, we have a dictionary that maps grades to lists of students.
We can look up the list of students who received a grade of 100, and then search through that list to find a specific student.
If the number of students who received a grade of 100 is small, this will still be very fast.
However, if there are many students who received a grade of 100, then we will have to search through each student to find the one we are looking for.
The time it takes to find a value in a list is still linear in the worst case, where all the students are in the list EXCEPT the one we are searching for.
We also have more overhead - this isn’t just a list or a dictionary, but many lists stored inside of a dictionary.
Each list requires additional memory, which can add up if you have a huge number of different grades (think about trying to account for grades like 99.45).
Choosing the right data structure is always a trade-off between factors like speed, data structure complexity, and memory usage.
When it comes to searching for a value, it doesn’t matter whether you organize your data in a list or a dictionary. There is a chance that you will have to look through every element in the list or dictionary to find what you are looking for. However, if you know the exact position of your element, then a list will be considerably faster. Alternatively, if you can organize your data with a unique key, then a dictionary will be very fast too. Computer Scientists have to think carefully about their use case and choose an appropriate data structure. Sometimes, we can organize our data using combinations of lists and dictionaries to get the best of both worlds, but it always requires critical thinking and experimentation to get it right.
There are many other data structures that can make various operations faster or slower. You will learn about many others down the road. For now, remember that lists are great when you need to go through many items in a specific order, and dictionaries are great when you need to look up a single item quickly. But neither data structure is perfect for every situation; if you need to search for a value, you will have to look through every element in the list or dictionary. Think carefully about your use case, and choose an appropriate data structure.