Boxes, Shelves, and Labels: Picking the Right Data Structure
Byte, a friendly luminous robot, stands in a tidy workshop beside a row of numbered cubbies bolted to the wall, an accordion-style stretchy shelf that expands as new binders are added, and a tray of labeled jars, smiling as glowing data tiles slot neatly into each one.
- Define arrays, lists, and dictionaries and identify how each stores related data.
- Compare the structures by how items are located: numeric index versus key label.
- Select the most suitable data structure for a given problem and justify the choice.
- Predict the output of an index lookup on a zero-indexed array or list.
- Distinguish dictionary lookup from list scanning and explain the efficiency difference.
Key terms
- Array
- A fixed-size, index-addressable collection allowing constant-time access by position.
- List
- A resizable indexed collection that can grow and shrink at runtime.
- Dictionary
- A key-value structure that retrieves values by unique key rather than position.
- Zero-based indexing
- The convention where the first element sits at index 0, not 1.
- Hashing
- Computing a key into a bucket location to give average constant-time lookup.
Why Index Access Is Constant Time
An array stores its elements in a contiguous block of memory, so the computer can compute any element's address directly as base_address plus index times element_size. That arithmetic takes the same time no matter how large the array is, which is why indexed reads are O(1). A list adds resizing, sometimes by allocating a larger block and copying elements when it grows, but indexed access remains constant time. This direct-address property is the defining strength of arrays and lists, and it is exactly what a dictionary trades away in exchange for key-based lookup.
Dictionaries and Key-Based Lookup
A dictionary maps unique keys to values using a hash function that converts each key into a storage location. On average this gives O(1) lookup, insertion, and deletion, dramatically faster than scanning a list one item at a time, which is O(n). The trade-off is that dictionaries do not preserve a meaningful positional order in the classic sense and rely on keys being hashable. Choose a dictionary when you naturally search by a name or ID rather than by counting positions, and choose an array or list when order and position drive your access pattern.
Worked examples
Evaluate scores[2] for scores = [10, 20, 30, 40] using zero-based indexing.
- Recall that indexing starts at 0, so scores[0] = 10 is the first element.
- scores[1] = 20 is the second element.
- scores[2] = 30 is the third element, since index 2 is the third position.
- Therefore the lookup returns 30, not 20, avoiding the off-by-one error.
Answer: scores[2] equals 30.
Activity
Match each real-world data need to the data structure that fits it best.
Practice
Choose the best structure to look up a student's grade by their unique student ID.
Given data = [5, 8, 13, 21], state the value returned by data[3].
Common mistakes to avoid
- The first index is oneMost languages use zero-based indexing, so the first element lives at index 0.
- Looping a list equals dictionary lookupScanning a list is O(n) per search while a dictionary gives average O(1) key lookup.
Check your understanding
In most programming languages, what is the index of the FIRST element in an array?
You are building a contacts app and need to look up a person's phone number by their name. Which structure fits best?
Which statement correctly describes a key difference between a classic array and a list?
What is the value of scores[2] if scores = [10, 20, 30, 40]?
A teacher wants to store 30 students and find any student's grade quickly by their student ID. Which choice is most appropriate?
Recap
Arrays and lists locate items by numeric index with constant-time access, arrays being fixed-size and lists resizable, while dictionaries locate values by unique key using hashing for average O(1) lookup. Match the structure to how you will search your data.
Reflect
For an app you have used, what data did it likely store as a dictionary rather than a list?