The map: 16 concepts in six groups

A metro map: first you see all the lines, then you ride station by station.

On top sit three basic ideas: Data Structure, Trade-off and Big-O. Below them, six groups: the Big-O growth shapes, the array, the hash map and set, structures with an order (stack and queue), structures with a shape (tree and graph), and finally how to choose among them in practice.

How to read this course

A passport: the same fields for everyone, so they're easy to compare.

Every concept gets the same treatment: its English name (the term you'll meet in docs and interviews), a picture from everyday life, a diagram and a card: what it is, how it works, an example, the cost, and how it relates to other structures. The one rule of this course: there is no best structure — only the one that fits the operation you do most.

Data Structure — organising 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.

The same task can be trivial or nearly impossible depending on how the data is held. Finding a word in a sorted dictionary takes seconds; finding it in the same words dumped in random order could take all day. So a surprising amount of "make this fast" is really "store it in the right shape." The structure is the decision.

Trade-off — every structure gives something up

A sports car and a moving van are both vehicles — you don't ask which is better, you ask better for what.

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. That's the trade-off: strength in one operation is paid for with weakness in another. There's no free lunch — your job is picking the trade that fits your use.

Big-O notation — 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 decides whether something stays fast at scale, so Big-O is how engineers compare approaches without ever running them.

Complexity classes — 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: the same time no matter the size (grabbing an item by index).
• O(log n) — logarithmic: barely grows even as data balloons (halving the search each step).
• O(n) — linear: grows in step with the data (scanning a list).
• O(n²) — quadratic: explodes (comparing every item to every other). The classic "fine in testing, dies in production."

For ten items, every structure feels instant — the differences don't show. Big-O is about what happens when n gets large. That's why things "suddenly" get slow in production: the bad shape was always there, just hidden until the data grew.

Array — 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 direct access by position is their superpower.

There's a price. Adding or removing at the end is cheap. But inserting or deleting in the middle shifts everything after it to keep the order and numbering intact — O(n).

Linear search — finding 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. That's linear search, O(n): slow for large lists. That gap is exactly the problem the next structure solves.

Hash Map — 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. A user by ID, a setting by name, a count by word — directly, by the key. Where an array forces you to know the position, a hash map lets you find by a meaningful name.

Hash function — why lookup is 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. The key goes through a hash function that computes where the value lives, so the map jumps straight there instead of searching. A million entries or ten, finding one is just as fast. That's why the hash map is the workhorse: "find by name" is what programs do constantly.

Set — present or not, no 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.

Stack — last in, first out (LIFO)

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) at 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).

Queue — first in, first out (FIFO)

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 (enqueue) and remove from the front (dequeue), 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).

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. Choosing between them is choosing the order your work comes back: reverse and nested (stack) or fair and sequential (queue). A small decision with a large effect — get the order right and the rest of the logic falls into place.

Tree — 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 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.

Balanced tree — search 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.

Graph — 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.

Dominant operation — choose by what you do most

You stock the kitchen by what you cook nightly, not by what looks impressive.

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.

Map before loop — reach for a map before 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.

How it all connects

A family tree of tools: each one covers a weakness of the one before.

Big-O is the ruler every structure is measured with. A Hash Map fixes the Array's weak spot (finding by value); a Set is a Hash Map without values. Stack and Queue are a sequence with the rule "take only from an end". A Tree adds hierarchy, and a balanced one searches in O(log n); a Graph lifts the last restriction and allows any links.