Express course · No. 23
A data structure is just a way of organising data so that the things you do most often are fast. Pick the right one and an operation is instant; pick the wrong one and the same task crawls. Big-O is the language for that difference — how the cost of an operation grows as the data grows. Learn a few structures and the notation, and 'why is this slow?' usually answers itself.
Essence only · One picture per idea · Learn the words
Before the specific structures, the idea behind all of them. A data structure isn't academic — it's the single choice that most often decides whether your code is fast or painfully slow.
A data structure organises data for the operations you do most
A tidy toolbox with labelled slots versus a heap of tools in a sack — the same tools, but one lets you grab the right one instantly and the other means digging every time.
A data structure is a way of arranging data in memory. Different arrangements make different operations fast: one is great at looking things up by name, another at keeping order, another at always grabbing the most recent item. The whole game is matching the structure to what you'll do most — because the arrangement that makes one operation instant often makes another slow. Pick for your common case.
The right structure turns hard into easy
Finding a word in a sorted dictionary takes seconds; finding it in the same words dumped in random order could take all day. Same data, the arrangement is everything.
The same task can be trivial or nearly impossible depending on how the data is held. Looking up a user by ID is instant in one structure and a slog through everything in another. So a surprising amount of "make this fast" is really "store it in the right shape." Choosing well up front often beats any amount of clever optimisation later — the structure is the decision.
Every structure is a trade-off
A sports car and a moving van are both vehicles — you don't ask which is better, you ask better for what. Speed in one thing is paid for with cost in another.
No structure is best at everything. One gives instant lookup but no order; another keeps order but is slow to search; another is fast to add to but slow to find within. Choosing means knowing what you're optimising for and what you're willing to give up. There's no free lunch — every structure trades strength in one operation for weakness in another, and your job is picking the trade that fits your use.
A data structure organises data so your common operations are fast. The right shape turns a hard task easy — and every structure trades speed in one operation for weakness in another.
To compare structures you need a way to talk about speed that doesn't depend on the machine. Big-O is that language: it measures how work grows as the data grows.
Big-O measures growth, not seconds
Asking not how long one delivery takes, but how the total time changes as the route goes from ten stops to ten thousand — the shape of the growth, not a stopwatch reading.
Big-O notation describes how the cost of an operation grows as the amount of data, called n, grows. It ignores the exact milliseconds and the specific computer, and captures the shape: does doubling the data double the work, quadruple it, or barely change it? That shape is what decides whether something stays fast at scale, so Big-O is how engineers compare approaches without ever running them.
The common shapes, from great to dreadful
Four ways a chore scales: one stays a single step no matter the pile, one grows with the pile, one explodes as the pile squared, and one barely grows even when the pile does.
A few shapes cover most code. O(1) — constant — takes the same time no matter the size (grabbing item by index). O(n) — linear — grows in step with the data (scanning a list). O(n²) — quadratic — explodes as data grows (comparing every item to every other), and is the classic "fine in testing, dies in production." O(log n) — logarithmic — barely grows even as data balloons (halving the search each step). Knowing which shape your operation is tells you if it will survive scale.
The shape only matters at scale
Two routes that are identical for a short trip diverge wildly over a long one — the difference is invisible until the distance is big enough to reveal it.
For ten items, every structure feels instant — the differences don't show. Big-O is about what happens when n gets large: at a million items, an O(n²) approach that was fine in your test is now grinding for minutes while an O(n) one finishes instantly. This is why things "suddenly" get slow in production: the bad shape was always there, just hidden until the data grew. Think about the shape before scale exposes it.
Big-O measures how work grows with the data, not raw seconds. O(1) and O(log n) survive scale; O(n) is honest; O(n²) is fine in testing and dies in production.
The most basic structure is the array, or list: an ordered sequence of items. Knowing exactly what it's fast and slow at sets the baseline for everything else.
An array is an ordered, numbered sequence
A row of numbered lockers: items sit in order, and each has a position — locker 0, locker 1, locker 2 — so you can go straight to any one by its number.
An array (or list) stores items in order, each at a numbered position called an index starting from 0. Because the items sit in a known, contiguous layout, jumping to any position by its index is instant — O(1). Arrays are the default for "a bunch of things in order," and that direct-access-by-position is their superpower. When you know where something is, you have it immediately.
Fast by position, slow to find by value
You can open locker 500 instantly — but if you only know what's inside and not which locker, you must open them one by one until you find it.
The catch: an array is fast only when you know the index. To find an item by its content — "is this email in the list?" — you have to check each one in turn, which is O(n), slow for large lists. So an array is perfect when you access by position and poor when you search by value. That gap is exactly the problem the next structure solves.
Inserting in the middle is costly
To slip a new book into the middle of a packed, numbered shelf, every book after it must shuffle down one spot to make room — a small insert, a lot of shifting.
Adding or removing at the end of an array is cheap, but inserting or deleting in the middle means shifting everything after it to keep the order and numbering intact — O(n). So arrays are ideal when you mostly read by position and append at the end, and a poor fit when you constantly insert and remove in the middle. Match them to access-by-index, append-heavy work.
An array is an ordered, indexed sequence: instant access by position, but O(n) to search by value or insert in the middle. Great for read-by-index, append-heavy work.
If one structure deserves to be your default workhorse, it's the hash map. It solves the array's biggest weakness — finding things by value — and it does it almost instantly.
A hash map stores key-value pairs
A phonebook: you look up a person by name and instantly get their number. You don't scan every entry — the name takes you straight to the answer.
A hash map (also called a dictionary, hash table, or just map) stores data as key-value pairs: you give it a key, it gives you the matching value. Look up a user by their ID, a setting by its name, a count by a word — directly, by the key. Where an array forces you to know the position, a hash map lets you find by meaningful name. It's the structure for "look this up by its identifier."
Lookup is effectively instant
A magic filing cabinet that, given a label, opens straight to the right drawer without checking the others — the number of drawers doesn't slow it down.
The magic of a hash map is that lookup by key is effectively O(1) — constant time, no matter how many items it holds. It uses the key to compute exactly where the value lives, so it jumps straight there instead of searching. A million entries or ten, finding one is just as fast. This is why the hash map is the workhorse: it makes "find by name" instant, which is what programs do constantly.
The set: membership without values
A guest list at a door — you don't need any details, only a yes-or-no: is this name on the list? Instantly checked, no scanning.
A close cousin is the set: a hash map that stores only keys, no values, to answer one question fast — "is this thing present?" Checking membership and avoiding duplicates are both O(1). Whenever you find yourself scanning a list to ask "have I seen this already?" a set turns that slow O(n) check into an instant one. Reach for it for uniqueness and fast membership tests.
A hash map finds a value by its key in effectively O(1) — the workhorse for lookup by identifier. Its cousin the set answers "is this present?" just as instantly.
Sometimes the order you take things out matters as much as what you store. Two structures formalise the two natural orders — and the difference between them is a single, intuitive rule.
A stack is last-in, first-out
A stack of plates: you add to the top and take from the top, so the last plate you put down is the first one you pick up.
A stack follows LIFO — last in, first out. You add ("push") and remove ("pop") from the same end, so the most recent item comes out first. This matches anything that nests or unwinds in reverse: an undo history, the back button, a program's call stack. Both operations are O(1). When the natural order is "most recent first," or "undo the last thing," you want a stack.
A queue is first-in, first-out
A line at a ticket counter: people are served in the order they arrived, newcomers join the back, and the front is served next.
A queue follows FIFO — first in, first out. You add at the back and remove from the front, so items are handled in arrival order. This is the structure for fairness and order: tasks to process, jobs waiting, requests to handle in turn — exactly the message-queue idea from the queues course. Like a stack, its operations are O(1). When order of arrival should be the order of handling, you want a queue.
The rule determines the behaviour
Same pile of work, two doors: one hands back the most recent item, the other the oldest. The single choice of which end changes everything downstream.
Stacks and queues hold the same kind of data; the only difference is which end you remove from, and that one rule shapes the whole behaviour. Choosing between them is choosing the order your work comes back: reverse and nested (stack) or fair and sequential (queue). It's a small decision with a large effect — get the order right and the rest of the logic falls into place.
A stack is last-in-first-out — undo, nesting, reversing. A queue is first-in-first-out — fair, in-order processing. Same data; the end you remove from is the whole difference.
The last two structures handle data that isn't a flat line but has shape — things that branch into hierarchies, or connect into networks. They're how you model relationships.
A tree is a hierarchy
A family tree or a company org chart: one thing at the top, branching down into children, each of which can branch further — structure that fans out, never loops back.
A tree organises data as a hierarchy: a root at the top, branching into nodes that have children, and so on down. It models anything nested — folders within folders, comments and their replies, a menu of categories. The branching shape mirrors the real-world nesting, which makes trees the natural fit whenever your data is "things inside things." Most hierarchies you meet in software are trees underneath.
A balanced tree searches in O(log n)
Finding a name in a phone book by opening the middle, then the middle of the right half, again and again — each step throws away half of what's left.
A well-organised (balanced) tree gives a powerful property: you can search it in O(log n) by repeatedly halving the space, the way you find a word in a dictionary without reading every page. That logarithmic shape barely grows even as data explodes — a billion items is only about thirty steps. This is how databases keep lookups fast at huge scale: ordered data in tree form, searched by halving.
A graph is a network of connections
A map of cities joined by roads, or people joined by friendships — things connected to each other in any pattern, with no top and no bottom.
A graph is the most general shape: nodes connected by edges, in any pattern, including loops. It models networks — social connections, roads between cities, links between pages, dependencies between tasks. Whenever the data is fundamentally "things related to other things" rather than a hierarchy or a line, it's a graph. Many hard, interesting problems — shortest route, who's connected to whom — are graph problems at heart.
A tree models hierarchy and, when balanced, searches in O(log n) by halving. A graph models a network of connections. Use them when data has shape — nested or linked.
You rarely build these from scratch — your language provides them. The skill is choosing the right one for the job, and knowing enough Big-O to feel a bad choice before it bites.
Choose by the operation you do most
You stock the kitchen by what you cook nightly, not by what looks impressive — the right tools are the ones for your actual, repeated work.
The practical decision is almost always: what operation will I do most, and which structure makes that fast? Looking up by key, constantly? Hash map. Need things in arrival order? Queue. Mostly reading by position? Array. Let the dominant operation pick the structure, and accept that it'll be slower at the things you rarely do. Optimise the common case; the structure is how.
Reach for a map before you reach for a loop
Before searching a crowd face by face for someone, you check if there's a guest list — the list answers instantly what the search does slowly.
A hugely common, hugely effective move: when you catch yourself scanning a list to find or match things — an O(n) loop, or worse an O(n²) loop inside a loop — ask whether a hash map or set could make it instant. Replacing a nested search with a map lookup is one of the most frequent real-world speedups there is. The structure, not a faster loop, is usually the fix.
- What operation dominates — lookup, ordering, add/remove — for this data? - Lookup by key? A hash map (or a set, for presence) is O(1). - Access by position, append-heavy? An array fits. - Order of removal matters — most recent (stack) or oldest (queue)? - Nested or networked data — a tree or a graph? - At scale, what's the Big-O — and is anything secretly O(n²)?
- data structure — a way of organising data so common operations are fast. - Big-O / n — how cost grows with the data size. - O(1) / O(n) / O(n²) / O(log n) — constant, linear, quadratic, logarithmic growth. - array / list / index — an ordered, numbered sequence; O(1) by position. - hash map / dictionary / set — key-value lookup and presence checks in O(1). - stack / queue / LIFO / FIFO — last-in-first-out and first-in-first-out. - tree / graph / node / edge — hierarchy and network; balanced trees search in O(log n).
- You pick the structure by the operation you do most, not by habit. - You reach for a hash map or set instead of scanning a list to find or dedupe. - You can name the Big-O of your hot path and you have no hidden O(n²). - You use a stack or queue when removal order matters, and a tree or graph when data has shape. - Things stay fast as the data grows, because you chose the shape before scale exposed it.
You don't build these from scratch — you choose them. Match the structure to the operation you do most, reach for a map before a loop, and let Big-O warn you before scale does.