Data Structures

What a data structure actually is

A way of arranging things, plus a promise about what that arrangement makes easy.

The four things you ever do to a collection

Access, search, insert and delete: the questions to ask about every structure in this course.

What computer memory actually looks like

Numbered boxes in a very long row, and why the numbering is the whole trick.

Why the layout decides the cost

Two ways to store the same five numbers, and what each one charges to reach an item.

What it costs to add and remove an item

Insertion and deletion flip the comparison the other way, and the pointers charge rent in memory.

The rule a structure promises to keep

Most structures are a layout plus a rule, and maintaining the rule is where the cost lives.

Counting steps instead of seconds

Why a stopwatch is the wrong tool for understanding a structure, and what to count instead.

How work grows when the data grows

Four patterns of growth, with real numbers, and why the distance between them is enormous.

The halving game, and what a logarithm is

Why throwing away half of what is left at each step makes even enormous collections small, and what that is worth when sorting.

Big O, read out loud

Attaching the standard names and notation to patterns you already understand.

Worst case and average case

The same operation has several honest costs, and it matters which one is being quoted.

Amortised cost, and why it is honest

How an occasional expensive operation can still leave every operation cheap on average.

When counting steps misleads you

Three situations where the cost on paper is not the cost you get, and what to do about it.