Choosing the Right Structure

Lesson 9 of 10 · 7 min · Free, no account needed

What you will learn

No structure is best at everything. Each is fast at some jobs and slow at others: a trade-off.
Find by key: dict. Is it in there: set. Newest first: stack. Oldest first: queue. Most urgent first: heap. In order by position: list.
Pick by the job you do most, and count the cost on a big n, like a million.
Real apps combine several structures, each doing the job it's best at.

One structure for everything?
A game app keeps 1 000 000 players: find one by name, add new scores, show the top 10.
Change what the app does most.
Slide from mostly finds to mostly top 10. Watch who wins. Visit all three marks.
A dict finds a key in one jump but has to scan everything for a top 10. A heap keeps the top on hand but has to scan to find a name. A real app keeps both and updates both.
Which structure is made for each job?
Everything from this course, in one place.
That's a trade-off.
A trade-off: getting faster at one thing by being slower at another. Every structure makes one.
With n = 1 000 000: one jump (dict, set) beats about 20 steps (heap, BST) beats a scan of n (a list search).
So ask: which job happens most? Then pick, or combine, the structures that make that job cheap.
Design the backend of a chat app.
Give each feature a structure. Make every meter fast, then Check.
A dict jumps to a name. A list keeps messages in the order you append them. A stack gives back the last edit. A heap keeps the top users ready.
Structure shop.
Jobs come in. Hand each one the structure it needs. Fast, with a streak.
This app lags. Fix it.
Someone stored everything in lists. Find the slow features and swap in better structures.
Inside a chatbot.
AI chatbots are built from the same structures. Match each part to its structure.
Load-test your backend.
Your design from earlier against "everything in a list", with 1 000 000 users.

Lessons are interactive and need JavaScript. Turn it on to play them.