800 Lost Items and a Line at the Desk: What a Data Structure Is
Keep a school lost-and-found's 800 items so the lunch line keeps moving: why one box, a list and A to Z order fall short, what a data structure is, and the trade-off every one of them makes.
Novice · Data Structures · Software Development · Updated
After this lesson you can
- Explain what a data structure is: a way of organizing data so the jobs you do most are fast
- Describe a trade-off between two ways of organizing the same data
- Choose how to keep a collection of things from the job done most often, and say what the choice makes slower
Key takeaways
- A data structure is a way of organizing data so the jobs you do most often are fast.
- The jobs you do with data, such as adding, finding and listing, are called operations.
- No structure is fast at everything. Making one job faster usually makes another one slower, and that's a trade-off.
- Choosing a data structure starts with one question: which job will I do most?
- With 800 items in one box, finding one can take 800 looks; on shelves kept by the kind people ask for, about 100.
It's lunchtime at a big high school, and 30 students are lined up at the lost-and-found desk. By spring the lost-and-found holds 800 things: water bottles, hoodies, textbooks, phone chargers, and one left mitten after another. Each student asks for something like "my water bottle, the blue one", and the volunteer behind the desk starts digging. Lunch lasts 30 minutes, and the line isn't moving.
There's no computer here yet, but it's the job a program does all day: keep a lot of things, and find one when someone asks. A music app finding a song, a shop finding an order and a game finding a player all have this desk's problem. So before any code, try to fix the desk.
What would you try?
Dig through the box. Everything goes into one big box. Adding is instant: toss it in. Finding the blue water bottle means looking at the items one at a time until it turns up: about 400 looks on an average day, and all 800 when it's at the bottom or not there at all. Thirty students at up to 800 looks each is up to 24,000 looks in one lunch.
Keep a list in the order things arrive. The volunteer writes each item on a clipboard as it's handed in, so finding means reading the list instead of digging. That's tidier, but it isn't faster: reading 800 lines is still 800 lines.
Keep everything in A to Z order by name. Now the blue water bottle sits among the other B's. But two things go wrong. Every item handed in has to be slotted into its place first, so adding gets slow. And students don't ask by the exact name: they ask for "a water bottle", "my hoodie", "a math book". The water bottles are scattered across the alphabet, from "Blue Water Bottle" to "Steel Water Bottle".
| What we tried | Add an item | Find "my blue water bottle" | Where it breaks |
|---|---|---|---|
| One big box | Toss it in | Up to 800 looks | The lunch line |
| A list in arrival order | Write one line | Up to 800 lines read | The lunch line |
| A to Z by name | Find its place first | Quick, but only by the exact name | The way students ask |
The questions that lead to it
What does the desk do most? Find: 30 times every lunch. Things are handed in a few times a day. So finding has to be fast, and adding can afford to be a little slower.
How do students ask? By kind: a bottle, a hoodie, a book, a charger.
So what if the way things are kept matched the way people ask? Put shelves behind the desk, one for each kind: Bottles, Books, Clothing, Sports, Electronics and so on. With 800 items over eight kinds, each shelf holds about 100. A student asks for a water bottle, the volunteer walks to the Bottles shelf and looks only there: at most about 100 looks instead of 800.
The lost-and-found in code
Here's a small version, with 8 items instead of 800, kept in a box and on shelves labeled by kind. The code finds the blue water bottle both ways and counts the looks. The shelves are written with your language's way of labeling things (a Dictionary, a Map, a dict, an object): a label, and the list of things under it. Module 5 shows how that works inside; here, picture labeled shelves.
List<string> box = new List<string> { "Red Umbrella", "Math Textbook", "Left Mitten", "Green Water Bottle", "Bike Helmet", "Phone Charger", "Blue Water Bottle", "Soccer Ball" };
Dictionary<string, List<string>> shelves = new Dictionary<string, List<string>>
{
["Bottles"] = new List<string> { "Green Water Bottle", "Blue Water Bottle" },
["Books"] = new List<string> { "Math Textbook" },
["Clothing"] = new List<string> { "Left Mitten" },
["Sports"] = new List<string> { "Bike Helmet", "Soccer Ball" },
["Other"] = new List<string> { "Red Umbrella", "Phone Charger" }
};
int boxLooks = 0;
foreach (string item in box)
{
boxLooks++;
if (item == "Blue Water Bottle")
{
break;
}
}
int shelfLooks = 0;
foreach (string item in shelves["Bottles"])
{
shelfLooks++;
if (item == "Blue Water Bottle")
{
break;
}
}
Console.WriteLine("In the box: " + boxLooks + " looks");
Console.WriteLine("On the Bottles shelf: " + shelfLooks + " looks");
In the box: 7 looks
On the Bottles shelf: 2 looks
void main() {
List<String> box = List.of("Red Umbrella", "Math Textbook", "Left Mitten", "Green Water Bottle", "Bike Helmet", "Phone Charger", "Blue Water Bottle", "Soccer Ball");
Map<String, List<String>> shelves = new HashMap<>();
shelves.put("Bottles", List.of("Green Water Bottle", "Blue Water Bottle"));
shelves.put("Books", List.of("Math Textbook"));
shelves.put("Clothing", List.of("Left Mitten"));
shelves.put("Sports", List.of("Bike Helmet", "Soccer Ball"));
shelves.put("Other", List.of("Red Umbrella", "Phone Charger"));
int boxLooks = 0;
for (String item : box) {
boxLooks++;
if (item.equals("Blue Water Bottle")) {
break;
}
}
int shelfLooks = 0;
for (String item : shelves.get("Bottles")) {
shelfLooks++;
if (item.equals("Blue Water Bottle")) {
break;
}
}
IO.println("In the box: " + boxLooks + " looks");
IO.println("On the Bottles shelf: " + shelfLooks + " looks");
}
In the box: 7 looks
On the Bottles shelf: 2 looks
box = ["Red Umbrella", "Math Textbook", "Left Mitten", "Green Water Bottle", "Bike Helmet", "Phone Charger", "Blue Water Bottle", "Soccer Ball"]
shelves = {
"Bottles": ["Green Water Bottle", "Blue Water Bottle"],
"Books": ["Math Textbook"],
"Clothing": ["Left Mitten"],
"Sports": ["Bike Helmet", "Soccer Ball"],
"Other": ["Red Umbrella", "Phone Charger"],
}
box_looks = 0
for item in box:
box_looks += 1
if item == "Blue Water Bottle":
break
shelf_looks = 0
for item in shelves["Bottles"]:
shelf_looks += 1
if item == "Blue Water Bottle":
break
print(f"In the box: {box_looks} looks")
print(f"On the Bottles shelf: {shelf_looks} looks")
In the box: 7 looks
On the Bottles shelf: 2 looks
const box = ["Red Umbrella", "Math Textbook", "Left Mitten", "Green Water Bottle", "Bike Helmet", "Phone Charger", "Blue Water Bottle", "Soccer Ball"];
const shelves = {
Bottles: ["Green Water Bottle", "Blue Water Bottle"],
Books: ["Math Textbook"],
Clothing: ["Left Mitten"],
Sports: ["Bike Helmet", "Soccer Ball"],
Other: ["Red Umbrella", "Phone Charger"],
};
let boxLooks = 0;
for (const item of box) {
boxLooks++;
if (item === "Blue Water Bottle") {
break;
}
}
let shelfLooks = 0;
for (const item of shelves["Bottles"]) {
shelfLooks++;
if (item === "Blue Water Bottle") {
break;
}
}
console.log(`In the box: ${boxLooks} looks`);
console.log(`On the Bottles shelf: ${shelfLooks} looks`);
In the box: 7 looks
On the Bottles shelf: 2 looks
const box: string[] = ["Red Umbrella", "Math Textbook", "Left Mitten", "Green Water Bottle", "Bike Helmet", "Phone Charger", "Blue Water Bottle", "Soccer Ball"];
const shelves: Record<string, string[]> = {
Bottles: ["Green Water Bottle", "Blue Water Bottle"],
Books: ["Math Textbook"],
Clothing: ["Left Mitten"],
Sports: ["Bike Helmet", "Soccer Ball"],
Other: ["Red Umbrella", "Phone Charger"],
};
let boxLooks = 0;
for (const item of box) {
boxLooks++;
if (item === "Blue Water Bottle") {
break;
}
}
let shelfLooks = 0;
for (const item of shelves["Bottles"]) {
shelfLooks++;
if (item === "Blue Water Bottle") {
break;
}
}
console.log(`In the box: ${boxLooks} looks`);
console.log(`On the Bottles shelf: ${shelfLooks} looks`);
In the box: 7 looks
On the Bottles shelf: 2 looks
Seven looks against two, for eight items. At 800 items the box could take 800 looks, while the Bottles shelf holds about 100. Both times the search is the same step-by-step method, look at each item until you find it, and a step-by-step way of doing a job is called an algorithm. What changed is how much of the pile the organization made it walk through.
How it got its name
Choosing how to keep things so the job you do most is fast is so central to programming that the choice has a name: a data structure. The data could be songs, contacts, orders or players; the structure is how they're kept. The jobs you do with the data (adding something, finding something, removing something, listing everything) are called operations.
You already know the idea from home. Socks go in a drawer, where you can grab a pair without looking. Papers go in labeled folders, so a tax form takes ten seconds to find. And there's the junk drawer, where anything can be tossed in a second, but finding the spare key means digging through everything. Same kinds of things, different ways of keeping them, and each makes a different job easy.

What got worse? The trade-off
So are shelves always better? Look at the other operations:
| Operation | The box | The shelves |
|---|---|---|
| Add a new item | Toss it in: instant | Decide what kind it is, find its shelf, put it there |
| Find the blue water bottle | Look through everything, up to every item | Look through one shelf |
| List everything in the order it arrived | It's all there in one pile | The order is lost: things were split onto shelves |
The shelves made finding faster, and paid for it by making adding a little slower and listing in order impossible. That give-and-take is called a trade-off: you gain on one job by giving something up on another. Every data structure in this course has one, and part of each lesson is learning what it is.
So the question is never "which structure is best?" It's "which job will I do most?" A lost-and-found where 30 students search every lunch wants shelves. A bin at a sports field that gets emptied once a week, without anyone searching it, is fine as a box.
Try it. Change the code to look for "Soccer Ball": in the box, and on the "Sports" shelf. Before you run it, predict both numbers.
Check yourself
2 questions to try on the lesson page.
So what
Every time you write a program that keeps more than a handful of things, you've chosen a data structure, even if you didn't think of it that way. From now on you'll choose on purpose: name the job you do most, and pick the structure that makes it fast.