How to choose a data structure

Start from the operations your code performs most, not from the structure you like.

Lesson 3 of 75 · Beginner 2 min read

Choosing well is a mechanical process, not taste. Answer four questions about your problem and the field narrows to one or two candidates.

1. What do you do most often?

Count the operations in the hot path: lookup by key, lookup by position, insert at the end, insert in the middle, delete, iterate in order, find the smallest.

2. Does order matter?

Insertion order, sorted order, or no order at all? Sorted order is expensive to maintain — do not pay for it unless you read it.

3. How large does it get?

At ten elements everything is fast and readability wins. At ten million, the difference between O(n) and O(log n) is the difference between a request and a timeout.

4. Do you need the values, or just membership?

Membership alone means a set. Keys with values means a map.

The cheat sheet

You need	Reach for	Why
Access by index	Array	O(1) by position, contiguous memory
Lookup by key	Hash map	O(1) average
Membership only	Set	O(1) average, no value stored
First in, first out	Queue	O(1) at both ends
Last in, first out	Stack	O(1) push and pop
Always the smallest or largest	Heap	O(log n) insert, O(1) peek
Sorted iteration plus fast lookup	Balanced BST	O(log n) both, ordered traversal
Prefix matching on strings	Trie	O(length of key)

Worked example

"Given a stream of events, report the 10 most recent per user."

Most frequent operation: append per user, read the last ten. Order matters, and it is recency. Keys are user ids.

That is a hash map from user id to a fixed-size queue — not an array of every event that you filter and sort on each read. The filter-and-sort version is O(n log n) per read and gets slower every day the system stays up.