# The right shape makes the hard part easy Express course on data structures and Big-O. 16 concepts — Data Structure, Big-O, Array, Hash Map, Set, Stack, Queue, Tree, Graph and more — each with its English name, a diagram, a card with an example and a cost, and how it relates to the rest. At the end, a cheat sheet: which structure for which operation. - **Author:** Fedor Chishchin - **Level:** intro - **Reading time:** ~30 minute read - **Published:** 2026-06-13 - **Source:** https://fedorthinks.com/learn/data-structures-express --- ## 1. Why structure matters 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. ### 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. _Diagram: Three basic ideas on top and six groups — chapters 2–7 follow them._ ### 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.** _Diagram: Same data: in a pile we check each one; in a map by id we jump straight there._ #### Data Structure (how data is laid out) - **What it is:** A way of arranging data in memory for particular operations. - **How it works:** The arrangement decides up front which operations are cheap and which are expensive. - **Example:** Looking up a user by ID: instant in one structure, a slog through everything in another. - **Cost:** A wrong choice isn't fixed by "clever optimisation" later. - **Related:** Structures are compared with **Big-O** and chosen through a **Trade-off**. ### 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. _Diagram: Each structure has its own strong side and its own weak side._ #### Trade-off (no free lunch) - **What it is:** A structure's strength in one operation always costs weakness in another. - **Example:** A **Hash Map** finds by key instantly but keeps no order; an **Array** keeps order but is slow to search by value. - **When to think:** Every time you decide where data lives: what do I do often, and what rarely? - **Related:** The trade is measured in **Big-O** — every operation has a "shape". > **The framing question:** "What operation will I do most on this data — look up, keep in order, add and remove — and which structure makes that one fast, even if it costs me elsewhere?" > 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. ## 2. Big-O: how cost grows 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 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. _Diagram: The bigger n gets, the further the shapes drift apart: O(1) and O(log n) stay nearly flat, O(n²) shoots up._ #### Big-O notation (asymptotic complexity) - **What it is:** A description of how work grows as the data size **n** grows. - **How it works:** Drop the exact seconds and hardware details; keep the shape of the growth. - **Example:** "Searching an array is O(n)": ten times more items — roughly ten times more work. - **Gotcha:** It doesn't tell you how many seconds; it tells you how it scales. - **Related:** The common shapes are the **Complexity classes**. ### 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. _Diagram: On ten test items all shapes look alike; on a billion there's a chasm._ #### Complexity classes (O(1), O(log n), O(n), O(n²)) - **What it is:** Names for the typical shapes of growth. - **Example:** Array index — O(1); balanced-tree search — O(log n); scanning a list — O(n); a loop inside a loop — O(n²). - **Gotcha:** O(n²) runs fine on test data and grinds for minutes on a million records. - **Rule:** O(1) and O(log n) survive scale; O(n) is honest; O(n²) is an alarm. - **Related:** **Map before loop** is the main way to turn O(n²) into O(n). > **The Big-O question:** "As this data grows large, what's the shape of this operation — does the work stay flat, grow with the data, or explode — and will that survive the real-world size?" > 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. ## 3. The array 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. ### 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)**. _Diagram: Know the index — open the right locker straight away._ _Diagram: Inserting in the middle shifts everyone after it; appending at the end is cheap._ #### Array (list, index) - **What it is:** Items in order, each with a numbered index from zero. - **Fast:** Access by index — O(1); appending at the end — cheap. - **Slow:** Search by value — O(n); insert or delete in the middle — O(n). - **Example:** A feed of posts read in order and appended to at the end. - **When to use:** You read by position and mostly append. - **Related:** Its weak spot — finding by value — is what a **Hash Map** fixes; **Stack** and **Queue** are often built on top of it. ### 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. _Diagram: Without an index we check one by one — in the worst case, the whole list._ #### Linear search (scan) - **What it is:** Check items one by one until you find the one you want. - **Cost:** O(n): ten times more data — ten times longer. - **Example:** `emails.includes(x)` on a list of a million addresses. - **Gotcha:** Inside another loop it becomes O(n²) — the classic "slow in production". - **Related:** Replaced by an O(1) lookup in a **Hash Map** or **Set**. > **The array question:** "Do I access this data by position and mostly append — where an array shines — or do I search by value and insert in the middle, where it's slow?" > An array is an ordered, indexed sequence: instant access by position, but O(n) to search by value or insert in the middle. ## 4. Hash Map and Set 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. ### 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. _Diagram: The key leads straight to the value — no looking through the other entries._ #### Hash Map (dictionary, hash table, map) - **What it is:** Key → value pairs with lookup by key. - **Fast:** Lookup, insert and delete by key — effectively O(1). - **Slow:** No order; finding "by value" rather than by key is a scan again. - **Example:** `users[id]`, `settings["theme"]`, word counts `counts[word] += 1`. - **When to use:** You constantly look things up by an identifier. - **Related:** Its speed comes from the **Hash function**; without values it becomes a **Set**. ### 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. _Diagram: The hash function turns a key into a slot number — the map goes straight there._ #### Hash function (hashing) - **What it is:** A function that computes, from a key, where its value sits in the table. - **How it works:** The same key always gives the same slot — so lookup never scans the entries. - **Example:** `hash("eve")` → slot 3 → that's where Eve's number is. - **Related:** The heart of **Hash Map** and **Set**. ### 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. _Diagram: A set answers yes-or-no in O(1) and never holds duplicates._ #### Set (membership) - **What it is:** A collection of unique keys with no values. - **Fast:** "Is it here?" and add — O(1); duplicates are dropped automatically. - **Example:** `seen = set()` — skip emails already sent; remove repeats from a list. - **When to use:** Uniqueness and fast membership tests. - **Related:** A **Hash Map** without the values. > **The map question:** "Am I looking things up by a meaningful key, or checking whether something's present — the jobs a hash map and set make instant, instead of scanning a list?" > 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. ## 5. Stack and Queue 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. ### 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)**. _Diagram: Push puts on top, pop takes from the top: the newest comes out first._ #### Stack (LIFO) - **What it is:** Add and remove only at the top. - **Fast:** `push` and `pop` — O(1). - **Example:** Undo in an editor, the browser back button, the call stack. - **When to use:** You need "most recent first" or "undo the last thing". - **Related:** Mirror of **Queue**: same data, other end for taking out. ### 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)**. _Diagram: Newcomers join the back, the front is served — in order of arrival._ #### Queue (FIFO) - **What it is:** Add at the back, take from the front. - **Fast:** `enqueue` and `dequeue` — O(1). - **Example:** Jobs for background workers, requests served in turn. - **When to use:** Order of arrival should be the order of handling. - **Related:** Mirror of **Stack**; at scale it grows into a message 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_. 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. _Diagram: Put in 1, 2, 3: a stack gives back 3, 2, 1, a queue gives 1, 2, 3._ > **The order question:** "Should the most recent item come out first (a stack, for undo and nesting) or the oldest (a queue, for fair, in-order processing)?" > 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. ## 6. Tree and Graph The last 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. ### 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. _Diagram: A file system is a tree: a root, folders as nodes, files as leaves, no loops._ #### Tree (root, node) - **What it is:** A hierarchy: every node can have children, but nothing loops back. - **Example:** Folders and files, a comment thread, a shop's category tree. - **When to use:** Your data is "things inside things". - **Gotcha:** Squeeze a hierarchy into a flat list and you'll be gluing it back together by hand. - **Related:** An ordered, even tree is a **Balanced tree**; a tree is a special case of a **Graph**. ### 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. _Diagram: Finding 62: bigger than 50 — go right, smaller than 75 — go left. Each step drops half._ #### Balanced tree (balanced search tree) - **What it is:** An ordered tree with the same depth on every side. - **How it works:** At each node, compare and go into one half — the other half is never looked at again. - **Fast:** Search — O(log n): a billion items ≈ 30 steps. - **Example:** Database indexes: ordered keys in tree form. - **Related:** A special **Tree**; unlike a **Hash Map**, it keeps order. ### 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. _Diagram: Nodes and edges in any pattern; loops are allowed — unlike a tree._ #### Graph (node, edge) - **What it is:** Nodes and the edges between them — no hierarchy, loops allowed. - **Example:** Friends in a social network, roads between cities, links between pages, task dependencies. - **Typical problems:** Shortest route; who is connected to whom. - **When to use:** The data is a network, not a line and not a hierarchy. - **Related:** A **Tree** is a graph with one root and no loops. > **The shape question:** "Is this data nested into a hierarchy (a tree) or connected as a network (a graph) — and am I modelling that shape, or forcing it into a flat list?" > 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. ## 7. How to choose 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. ### 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. _Diagram: Name your most frequent operation — it points to the structure._ #### Dominant operation (optimise the common case) - **Idea:** The most frequent operation picks the structure, not habit. - **Example:** Thousands of user-by-ID lookups per second → **Hash Map**, even though order is lost. - **Cost:** Rare operations get slower — a deliberate trade. - **Related:** **Trade-off** applied in practice. ### 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. _Diagram: Before: a loop in a loop, a million checks. After: build the map once, then O(1) per lookup._ #### Map before loop (lookup instead of nested scan) - **Problem:** For each item we scan another list — O(n²), slow in production. - **Idea:** Build a **Hash Map** or **Set** once, then look up in it at O(1). - **Example:** Instead of `users.find(u => u.id === order.userId)` inside a loop over orders — build `byId` first and use `byId[order.userId]`. - **Cost:** A little memory for the map. - **Related:** Turns a **Linear search** inside a loop into O(1). #### Before you pick a structure - **What operation dominates** — lookup, ordering, add/remove? - **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²)? #### Signs you choose well - 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. ### 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. _Diagram: Big-O measures them all; each structure answers a weakness or a limit of its neighbour._ ## Cheat sheet: all 16 concepts ### Basics - **Data Structure** (how data is laid out): A way of arranging data so your common operations are fast. - **Trade-off** (no free lunch): Strength in one operation costs weakness in another. ### Big-O - **Big-O notation** (asymptotic complexity): How work grows as the data size n grows. - **Complexity classes** (O(1), O(log n), O(n), O(n²)): Constant, logarithmic, linear, quadratic. O(n²) is an alarm. ### Array - **Array** (list): In order, with an index: O(1) by position, O(n) to insert in the middle. - **Linear search** (scan): Find by value by checking one by one. O(n). ### Hash map - **Hash Map** (dictionary, map): Key → value, lookup by key effectively O(1). No order. - **Hash function** (hashing): Computes from the key where the value lives — so no scanning. - **Set** (membership): Keys only: "is it here?" in O(1), no duplicates. ### Order - **Stack** (LIFO): Last in, first out. Undo, back button, call stack. - **Queue** (FIFO): First in, first out. Processing in arrival order. ### Shape - **Tree** (hierarchy): Root, nodes, children, no loops. - **Balanced tree** (balanced search tree): Search by halving — O(log n). How database indexes work. - **Graph** (network): Nodes and edges in any pattern. Networks, routes, dependencies. ### How to choose - **Dominant operation** (common case): The most frequent operation picks the structure. - **Map before loop** (lookup over scan): Before a nested scan — build a Hash Map or Set. > 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. End of express course · 7 chapters · 16 concepts Next comes practice: find a spot in your code where you loop through a list to find or match something, and replace it with a hash map or set lookup — then notice how much faster it is on large data. Then, for one slow operation, work out its Big-O and ask whether a different structure changes the shape. But hold one idea above the rest: the right shape makes the hard part easy. Most "why is this slow?" answers are really "it's in the wrong structure" — and choosing the right one is the cheapest speed you'll ever buy.