Practice question · Multiple choice
A list preserves order and allows duplicates; a set does neither and can test membership far faster. Why does giving up order and duplicates buy speed?
Hints
- Ask what a list must preserve, and whether that leaves it any freedom in where to store things.
- How does a set decide where to put an element?
Show the answer
A. Because a set can store elements by hash, so membership is a direct lookup.
Why
A list promises that element i is at position i, which fixes where everything is stored and leaves nothing to exploit. A set makes no such promise, and that freedom is what it trades for speed, hash the element and compute the location. A sorted structure is a third point on the same trade-off, giving O(log n) membership and ordered traversal.
Practise Basic Data Collections
The app has 7 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.
More questions on Basic Data Collections
- Select every statement that is true of lists and dictionaries as the lesson describes them.
- For a list of length 4 (valid indices 0 through 3), sort each index by whether accessing it is valid.
- A list stores elements by sequential position, whereas a dictionary associates values with unique keys. What…