Why Data Structures and Algorithms Matter

Table of Contents

1. A Page That Got Slow
2. Data Structures and Algorithms, Defined
3. Where You Meet Them at Work
4. Big-O in Five Minutes
5. Set Up the algolab Project
6. Your First Benchmark: includes vs Set
7. The Structure Is the Speed
8. Time Versus Memory
9. How to Use This Series
10. Recipe: The bench Module
11. Try It Yourself

1. A Page That Got Slow

Here is a story that happens on almost every team. A developer builds an admin page that shows a list of orders, and next to each order it shows the customer's name. The code is simple:

interface Customer {
  id: number;
  name: string;
}

interface Order {
  id: number;
  customerId: number;
  total: number;
}

function attachNames(orders: Order[], customers: Customer[]) {
  return orders.map((order) => {
    const customer = customers.find((c) => c.id === order.customerId);
    return { ...order, customerName: customer?.name ?? "unknown" };
  });
}

With 50 orders and 20 customers in the test database, it runs instantly. A year later the shop has 20,000 customers and 200,000 orders. The same function now does up to 200,000 times 20,000 comparisons, which is four billion steps. The page takes half a minute and the server fan spins up.

Nobody wrote a bug. The code is correct. It is just built on the wrong data structure: a plain array that has to be searched from the start every time. Keep the customers in a Map keyed by id, and every lookup becomes a single step:

function attachNamesFast(orders: Order[], customers: Customer[]) {
  const byId = new Map<number, Customer>();
  for (const c of customers) byId.set(c.id, c);

  return orders.map((order) => ({
    ...order,
    customerName: byId.get(order.customerId)?.name ?? "unknown",
  }));
}

The new version does 20,000 steps to build the map, then 200,000 quick lookups. About a quarter of a million steps instead of four billion. Same output, a different arrangement of the data. That one change is what this whole series is about.

2. Data Structures and Algorithms, Defined

Two words, two ideas.

A data structure is a way of organizing data in memory so that some operations are cheap. An array keeps items in a row so you can jump to any position. A hash map keeps key-value pairs so you can find a value by its key. A stack keeps items so you can only touch the newest one. Each structure is a set of trade-offs: it makes some operations fast and others slow, and there is no structure that is best at everything.

An algorithm is a precise list of steps that solves a problem. "Look at each item, remember the largest so far, return it" is an algorithm for finding a maximum. "Cut the sorted list in half until you find the target" is the algorithm called binary search.

The two are partners. An algorithm needs somewhere to keep its data, and a structure is only useful if there are good algorithms to work with it. You will see this over and over: the clever step in an algorithm is usually "put the data in a structure where this question is cheap".

Two more points before we go on.

• Correct comes first, fast comes second. An algorithm that returns wrong answers quickly is worthless. Every chapter shows you the simple version first and only then speeds it up.
• You almost never invent these. Computer scientists have studied these problems for decades. Your job is to recognize which known tool fits, and to know what it costs.

3. Where You Meet Them at Work

You may be thinking: "I use Array and Map every day and never think about it." That is true, and it is why these topics are worth a few chapters. Almost every piece of software you touch is a data structure in disguise:

You will also meet them in technical interviews. Interviewers ask about arrays, hash maps, trees, and graphs not because your job will be reversing linked lists all day, but because a small problem shows how you break something down, test it, and judge its cost. This series teaches the content and gives you a method for that in the last chapter.

4. Big-O in Five Minutes

To compare two approaches we need a way to describe their cost that does not depend on whose laptop runs it. That is Big-O notation. It describes how the number of steps grows as the input size n grows. The full story is in Big-O Notation from the Math for Programmers series. If you have read it, this is a quick reminder. If you have not, read this section and then skim that chapter.

The three rules you need today:

1. Count the loops. One loop over the input is O(n). A loop inside a loop, both over the input, is O(n^2). Halving the problem each step is O(log n).
2. Hidden loops count. arr.includes(x), arr.indexOf(x), arr.find(...), arr.slice(), and string.includes(...) all loop internally. Call one of them inside your own loop and you have O(n^2). That was the bug in section 1: customers.find is the hidden loop.
3. Drop constants and small terms. 3n + 7 is just O(n). Big-O describes the shape of growth, not the exact time.

Big-O is a prediction about growth. It is not a stopwatch. Always remember that for tiny inputs a "worse" algorithm can be faster, and that real code also cares about memory and readability. But when data grows, the shape wins.

5. Set Up the algolab Project

Over this series you build a small library called algolab. Each chapter adds a TypeScript module and a test file. We run everything with Node.js, with no build step and no browser.

Make sure Node is installed (the LTS version is fine):

node --version

You should see something like v22.x or higher. Now create the project:

mkdir algolab
cd algolab
npm init -y
npm install --save-dev typescript tsx @types/node
mkdir src

tsx is a tool that runs TypeScript files directly in Node, so there is no compile step. typescript gives you type checking, and @types/node teaches TypeScript about built-in names such as performance and node:test.

Open package.json and make two changes: add "type": "module" so Node treats your files as modern ES modules, and replace the scripts section with a test script and a type-check script. The file should look like this (your version numbers will differ):

{
  "name": "algolab",
  "version": "1.0.0",
  "type": "module",
  "private": true,
  "scripts": {
    "test": "tsx --test",
    "typecheck": "tsc"
  },
  "devDependencies": {
    "@types/node": "^22.0.0",
    "tsx": "^4.0.0",
    "typescript": "^5.0.0"
  }
}

Next create tsconfig.json in the same folder:

{
  "compilerOptions": {
    "target": "ES2022",
    "module": "NodeNext",
    "moduleResolution": "NodeNext",
    "strict": true,
    "noEmit": true,
    "allowImportingTsExtensions": true,
    "skipLibCheck": true,
    "types": ["node"]
  },
  "include": ["src", "demo.ts"]
}

What these settings do:

• strict turns on all of TypeScript's safety checks. Leave it on.
• noEmit means tsc only checks types and never writes .js files. tsx handles running.
• allowImportingTsExtensions lets us write import ... from "./bench.ts", which is what Node and tsx expect when running TS files directly.

You now have this layout:

algolab/
  package.json
  tsconfig.json
  src/
    (modules and tests will go here)
  demo.ts        <- you will create this

Check that everything is wired up. Create hello.ts:

const message: string = "algolab is ready";
console.log(message);

Run it:

npx tsx hello.ts

algolab is ready

You can delete hello.ts now. Two commands you will use constantly:

• npx tsx demo.ts runs a file.
• npm test runs every *.test.ts file with Node's built-in test runner. No testing library to install.

6. Your First Benchmark: includes vs Set

Let us prove, with a stopwatch, that the structure you choose changes the speed. Both Array and Set can answer "is this value in here?", but they do it differently:

• array.includes(x) walks the array from the start until it finds x. In the worst case it looks at every item: O(n).
• set.has(x) computes where x would be stored and checks only that spot. On average it takes O(1). (Chapter 3 shows how that works.)

Make a file demo.ts in the project root:

// demo.ts
const arr = Array.from({ length: 1_000_000 }, (_, i) => i * 2);
const set = new Set(arr);
const target = arr[arr.length - 1]; // the last item: worst case for the array

let start = performance.now();
for (let i = 0; i < 100; i++) arr.includes(target);
const arrayMs = performance.now() - start;

start = performance.now();
for (let i = 0; i < 100; i++) set.has(target);
const setMs = performance.now() - start;

console.log("array.includes x100:", arrayMs.toFixed(3), "ms");
console.log("set.has x100:       ", setMs.toFixed(3), "ms");
console.log("set is faster:", setMs < arrayMs);

Run it with npx tsx demo.ts. On one laptop the output was:

array.includes x100: 13.952 ms
set.has x100:        0.032 ms
set is faster: true

Your two timings will be different, and that is normal. What should not change is the ordering and the rough size of the gap: the Set is hundreds of times faster here. The array scanned a million items 100 times. The Set did 100 quick lookups.

Now make the data ten times bigger. Change 1_000_000 to 10_000_000 and run again. The array time grows roughly ten times (that is O(n) at work), and the Set time hardly moves (that is O(1)). This is what Big-O means in practice: not a number, a trend.

A few honest notes on benchmarks, which apply to the whole series:

• Timings are noisy. Compare ratios, not exact milliseconds, and run more than once.
• The first run is often slower, because the JavaScript engine is still optimizing your code. Repeat the work, as we did with the loop of 100.
• Test the worst case on purpose. Searching for the last item shows the true cost of a linear scan. Searching for the first item makes any array look fast.

7. The Structure Is the Speed

The previous benchmark is one example of a general idea: the cost of an operation depends on the structure that holds the data. Here are the costs for the things you already use. Treat this as a preview; each structure gets its own chapter.

Neither column wins everywhere. An array is perfect for "give me item 5" and for iterating in order. A Set or Map is perfect for "is this in here?" and "what goes with this key?". Choosing well means asking three questions about your problem:

1. What operation will I do most often: read by position, search by value, add, remove, or go through everything in order?
2. Does order matter? (First in, first out? Sorted?)
3. How big can the data get? For 20 items, anything works. For 20 million, the shape matters.

You can see the "remove from the start" cost for yourself. This code removes 100,000 items one at a time, first from the end, then from the front:

const fromEnd = Array.from({ length: 100_000 }, (_, i) => i);
let t = performance.now();
while (fromEnd.length > 0) fromEnd.pop();
console.log("pop:  ", (performance.now() - t).toFixed(1), "ms");

const fromFront = Array.from({ length: 100_000 }, (_, i) => i);
t = performance.now();
while (fromFront.length > 0) fromFront.shift();
console.log("shift:", (performance.now() - t).toFixed(1), "ms");

pop:   0.6 ms
shift: 672.8 ms

Same array, same 100,000 items, and removing from the front took roughly a thousand times longer on this machine. shift has to move every remaining item one place left, so it costs O(n) each time, and a loop of them is O(n^2). Chapter 2 explains why, and Chapter 5 builds a queue that avoids the problem.

8. Time Versus Memory

Most speedups spend memory. The fast Map in section 1 uses extra memory to hold every customer. The Set in the benchmark holds a second copy of the million numbers. This trade is called time versus space, and it shows up everywhere:

Space complexity uses the same Big-O notation to describe extra memory. A loop with a counter uses O(1) space. A Set that might hold every input item uses O(n).

So the honest answer to "which is best?" is nearly always "it depends on what is scarce". A phone with little memory might prefer the slower, leaner version. A server answering a million requests a minute almost certainly prefers the fast one. Knowing the costs lets you choose on purpose instead of by accident.

9. How to Use This Series

Every chapter follows the same rhythm, so you always know where you are:

1. A real problem. Why the structure exists and where you meet it.
2. The idea. Explained with small examples and outputs you can run.
3. A cost table. The Big-O of each operation.
4. Interview-style problems. Typical questions, solved step by step.
5. A recipe. You add a module and tests to algolab.
6. Try It Yourself. Exercises, some interview-style.

A few tips to get the most from it:

• Type the code. Do not paste it. Typing slows you down enough to notice what each line does.
• Predict, then run. Before running an example, write down what you think it prints. When you are wrong, you learn the most.
• Draw it. For arrays, lists, trees, and graphs, a quick sketch on paper beats staring at code.
• Run the tests often. npm test after every change catches mistakes while they are still small.
• Do the exercises. Reading about an algorithm and being able to write it from a blank file are very different skills.

Plan for an hour or two per chapter. The first time through, aim to understand rather than to memorize. Real mastery comes from meeting the same ideas in several different problems, and the series is built to do exactly that.

10. Recipe: The bench Module

Time to write the first module. Create src/bench.ts:

// src/bench.ts

export interface Timing<T> {
  label: string;
  ms: number;
  result: T;
}

// Run fn once and report how long it took.
export function time<T>(fn: () => T, label = "task"): Timing<T> {
  const start = performance.now();
  const result = fn();
  const ms = performance.now() - start;
  return { label, ms, result };
}

// O(n): look at items one by one.
export function linearSearch<T>(items: T[], target: T): number {
  for (let i = 0; i < items.length; i++) {
    if (items[i] === target) return i;
  }
  return -1;
}

// O(n^2): compare every pair.
export function hasDuplicateSlow(nums: number[]): boolean {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] === nums[j]) return true;
    }
  }
  return false;
}

// O(n): remember what we have seen in a Set.
export function hasDuplicateFast(nums: number[]): boolean {
  const seen = new Set<number>();
  for (const n of nums) {
    if (seen.has(n)) return true;
    seen.add(n);
  }
  return false;
}

time is generic: <T> means "whatever type fn returns, the result field has that same type". linearSearch returns the index of the first match, or -1 when the target is missing, which is the same convention as Array.prototype.indexOf.

Now add the tests. Create src/bench.test.ts:

// src/bench.test.ts
import { test } from "node:test";
import assert from "node:assert/strict";
import {
  time,
  linearSearch,
  hasDuplicateSlow,
  hasDuplicateFast,
} from "./bench.ts";

test("linearSearch finds the index or returns -1", () => {
  assert.equal(linearSearch([5, 7, 9], 9), 2);
  assert.equal(linearSearch([5, 7, 9], 4), -1);
});

test("both duplicate checkers agree", () => {
  const cases = [[], [1], [1, 2, 3], [1, 2, 1], [4, 4]];
  for (const c of cases) {
    assert.equal(hasDuplicateSlow(c), hasDuplicateFast(c));
  }
  assert.equal(hasDuplicateFast([1, 2, 1]), true);
});

test("time returns the result and a non-negative duration", () => {
  const t = time(() => 2 + 2, "add");
  assert.equal(t.result, 4);
  assert.equal(t.label, "add");
  assert.ok(t.ms >= 0);
});

Run the tests:

npm test

You should see all three tests pass (the last lines of the report show # pass 3 and # fail 0). Run the type checker too with npm run typecheck. It prints nothing when everything is fine.

Now replace demo.ts with a version that uses the module:

// demo.ts
import {
  time,
  linearSearch,
  hasDuplicateSlow,
  hasDuplicateFast,
} from "./src/bench.ts";

console.log("--- bench ---");
const arr = Array.from({ length: 1_000_000 }, (_, i) => i * 2);
const set = new Set(arr);
const last = arr[arr.length - 1];

console.log(linearSearch(arr, last)); // 999999
console.log(linearSearch(arr, 7));    // -1 (7 is odd, so it is missing)

const withArray = time(() => {
  for (let i = 0; i < 100; i++) arr.includes(last);
}, "includes x100");
const withSet = time(() => {
  for (let i = 0; i < 100; i++) set.has(last);
}, "set.has x100");

for (const r of [withArray, withSet]) {
  console.log(r.label.padEnd(16), r.ms.toFixed(3), "ms"); // varies
}
console.log("set faster than array:", withSet.ms < withArray.ms); // true

const small = Array.from({ length: 20_000 }, (_, i) => i);
const slow = time(() => hasDuplicateSlow(small), "slow dup check");
const fast = time(() => hasDuplicateFast(small), "fast dup check");
console.log(slow.label.padEnd(16), slow.ms.toFixed(1), "ms"); // about 75 ms
console.log(fast.label.padEnd(16), fast.ms.toFixed(2), "ms"); // about 1 ms
console.log(slow.result, fast.result); // false false

Run npx tsx demo.ts. The two search results, the true line, and the false false line are stable. The millisecond numbers will differ from machine to machine, but the ordering will match: the Set and the Set-based duplicate checker are far faster. Our array of 20,000 distinct numbers has no duplicates, so both checkers give the full amount of work and both return false.

11. Try It Yourself

1. Spot the hidden loop. Which of these is O(n^2) and why? (a) for (const x of a) if (b.includes(x)) count++; (b) for (const x of a) if (setB.has(x)) count++; (c) a.map(x => x * 2).filter(x => x > 10). Assume a and b both have n items.
2. Find the break-even. Using time from src/bench.ts, compare hasDuplicateSlow and hasDuplicateFast on arrays of 100, 1,000, and 10,000 distinct numbers. At what size does the Set version start to win clearly? Is the Set ever slower?
3. Fix the orders page. Write the section 1 attachNames and attachNamesFast as real functions in src/orders.ts. Generate 2,000 customers and 20,000 orders with a loop and time both. Check that they produce equal output with assert.deepEqual.
4. Measure shift. Repeat the pop versus shift test with 10,000 and then 100,000 items. When the size grows 10 times, how many times slower does shift get? Does that match O(n^2) for the whole loop?
5. Interview-style: first repeated value. Given an array of numbers, return the first value that appears twice when reading from left to right, or undefined if none repeats. For [2, 5, 1, 2, 3, 5] the answer is 2. First write the obvious O(n^2) version, then an O(n) version, and state the extra memory each one uses.
6. Interview-style: sorted or not. Someone says "I will sort the list, then binary search it, because binary search is O(log n) and that beats O(n)." If the list is searched only once, are they right? What if it is searched ten thousand times? Explain in two sentences, using the cost of sorting.

You now know why this series exists: the arrangement of your data decides how fast your code runs, and Big-O is the language for talking about it. The first everyday structure is the one you use most. Next up is Arrays and Strings, where we look at how arrays live in memory, why shift is slow, and three techniques (two pointers, sliding window, and prefix sums) that solve a large share of interview problems.