Data Structures
You have one thing: a long row of numbered boxes. That's all a computer's memory really is. Everything else is something people invented on top of those boxes: the list that grows, the map that finds a name instantly, the tree that stays sorted. In this course you build each of them yourself.
Each structure here is a working one you operate yourself. You insert into a real tree and watch it lean over. You hand a table two different names that it wants to file in the same place, and watch how it copes. At the end you race all six on data you pick, and the speeds are counted as the code runs rather than copied from a table.
The steps
Memory is a numbered street
Before any of the names and labels a program puts on top, the bottom layer is very simple. A computer's
memory is a single enormously long row of numbered slots. Slot 0, slot 1, slot 2, on and on for billions.
Each slot holds a number. That is the whole inventory. A run of those slots, all the same size, sitting
side by side and holding one collection of things, is called an array. Its slots are numbered from
0, and that number is called the index. Programmers write the index in square brackets after the
array's name, so scores[3] means the item at index 3 of an array called scores. Counting from
0 takes some getting used to: scores[3] is the fourth item along, not the third.
So when you write scores[3] and get an answer instantly, what actually happened? Not
searching. The machine did one piece of arithmetic:
address = start_of_array + (index × size_of_each_item)
One multiply, one add, one fetch. It costs the same whether you ask for slot 2 or slot 2,000,000. That is the entire reason arrays feel instant, and the first thing worth understanding about every structure that follows.
What a byte is, and why 4 of them
A bit is one switch: 0 or 1. Eight of them together is a byte, which can hold 256 different patterns, so it covers 0 to 255.
One byte is not enough for most numbers, so computers usually store a whole number in four bytes side by side. That is where the 4 comes from. It is not a law of nature, just the size this particular machine chose.
Say that again with a street
Picture a street where every house is exactly 4 metres wide and the first one starts at metre 4000. You want house number 10. You do not walk down the street counting houses. You work out 4000 + 10 x 4 = 4040 and go straight there.
That is the whole trick, and it is why the answer takes the same time whether you want house 10 or house 10,000.
Why addresses are written like 0x1F98
Addresses are usually printed in hexadecimal, counting 0 to 9 then A to F, so sixteen digits instead of ten. One hex digit covers exactly four bits, which means two of them describe one byte precisely. That tidiness is the only reason it is used.
Nothing later depends on being able to read hex, so skip it happily if it is not clicking today.
An array is fast at finding things by position because position is arithmetic. It is slow at almost everything else, and the rest of this course is a series of increasingly clever answers to "but what if I don't know the position?"
a[10] live?When arrays hurt
Arrays have a hidden condition attached: the items must sit next to each other, in order, with no gaps. That is what makes the address arithmetic work. It is also what makes them painful.
Insert something at the front, and there is nowhere to put it: every other item has to shuffle one slot to the right to make room. Delete from the front, and everything shuffles back. Try both below and watch the counter.
Show me the shuffling with five names
Say the slots hold Ana, Ben, Cy, Dee, Eve, and you delete Ana. Ben has to move into slot 0, Cy into slot 1, Dee into slot 2, Eve into slot 3. Four items moved to remove one.
Delete Ben next and three items move, then two, then one. Ten moves in total to empty a list of five, and none of that work shows up in the one line of code that says "delete".
What a loop is
A loop is an instruction to do the same lines again and again:"delete the front item, and keep doing that until nothing is left". Programs are full of them, because that is how one line of writing gets a computer to do a million things.
The cost of a loop is the cost of what is inside it, multiplied by how many times round it goes. That multiplication is the whole point of this step. One shuffle is nothing. One shuffle inside a loop that runs a million times is not nothing at all.
"Remove this item from the middle of a list" is one of the most ordinary things a program does. On an array of a million items, doing it in a loop a million times is not a million operations: it's closer to half a trillion. Programs that mysteriously crawl are very often doing exactly this.
Adding 1 + 2 + 3 all the way up to the last one
Through the rest of this course, the letter n is a stand-in for "however many items you are holding". A thousand names, a million rows: whatever the number happens to be, we write n, and work out the shape of the answer once rather than redoing the sum for every size. So"1 + 2 + 3 all the way up to n" means adding up every number from 1 to however many you have.
Pair the first number with the last: 1 + 999 = 1000. Then 2 + 998 = 1000. Every pair comes to the same total, and there are about half as many pairs as numbers, so the whole sum is about n times n divided by 2. For n = 1000 that is roughly 500,000, and for n = 1,000,000 it is about 500,000,000,000, which is where the half a trillion above comes from.
The array that grows itself
There's a second problem. To lay items out end to end, the machine has to reserve the space up front. So how big? Guess too small and you run out. Guess too big and you waste memory you never use.
The fix is the dynamic array, the thing you actually use when you write list in
Python, ArrayList in Java, vector in C++, or [] in JavaScript. When
it fills up, it allocates a bigger block, copies everything across, and carries on. The clever part is
how much bigger. Adding one item to the end of an array is such a common thing to do that it has
its own name: a push. Taking the last one back off again is a pop. Those two words are used
by every programming language there is, and by every counter in the lab below.
What Python, Java and C++ are
Those are programming languages: four different ways of writing instructions for a computer, each with its own vocabulary and its own habits. Sinhala and English are both languages for saying things, and it is the same idea. You do not need any of them for this course.
They are named here only to make one point. Four languages designed by different people at different times all shipped the same structure, because the problem it solves comes up in every program ever written. The names differ, and the thing underneath is the array that grows itself, doubling exactly as the lab below does.
What "allocates a block" means
Asking for memory means asking for a run of slots that nobody else is using, starting at some address. Once you have it, the slots on either side belong to somebody else, so the block cannot be stretched later.
That is why growing is a move rather than an extension: the machine finds a bigger free run somewhere else, copies the items into it, and gives the old run back.
Individual pushes are not all equal: most are instant, and occasionally one is expensive. But because the expensive ones get rarer at exactly the rate they get costlier, the average over any run of pushes stays constant. That's called amortized O(1): you get the convenience of a growing list for roughly the price of a fixed one.
Reading O(1) and O(n), before Step 14 does it properly
Step 2 already gave the letter n its job: however many items you happen to be holding. O(1) means the cost stays the same however big n gets, so one slot lookup is one slot lookup whether you hold ten items or ten million. O(n) means the cost climbs in step with n, so ten times the items is ten times the work.
Read it as the shape of the cost rather than a number of seconds. Step 14 puts real counters on these and draws the shapes.
Why doubling only ever happens a handful of times
Start with room for 1 and keep doubling: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024. Ten doublings and you already hold a thousand. Ten more and you hold a million.
Each doubling costs one full copy, so a million pushes cost about twenty copies in total. Growing by one instead would cost a copy on every single push, which is a million of them.
Telling the array what to do
Every lab so far has been buttons, and a button does one thing once. That is fine for watching a single insert. But the costs in the last two steps only became interesting when the same small thing happened ten thousand times, and nobody presses a button that often. So before leaving the array behind, it is worth having a way to tell it what to do in writing, and to count what that costs while it happens.
A program is a list of instructions, written down in order, that something else carries out
exactly as written. That is the whole idea. The pad below understands nine instructions and a few ordinary
words like if and while. It does them one at a time, in the order you wrote
them, so you can watch each one land. Three of the nine are enough to begin with. push(7) puts 7 on
the end of the row, get(2) reads the value in slot 2, and log(x) prints
something in the output underneath.
Writing the same line three times over is allowed, and dull, so every language has a shorthand for it. These two halves do exactly the same thing:
push(1)
push(1)
push(1)
for (i = 0; i < 3; i = i + 1) {
push(1)
}
How do I read that for line
The three parts inside the brackets, separated by semicolons, are the setup, the question and the
change. Start a counter called i at 0. Before each go round, ask whether i is still under
3, and stop when it is not. After each go round, add one to i. The lines between the curly brackets are
the body, and the body is what gets repeated.
The name i is not special, it is just a name someone made up long ago and everybody
copied. What matters is that changing the 3 to 10000 changes nothing else about the program, and the
machine does not mind in the slightest. That is the whole reason for writing instructions rather than
pressing a button.
insertAt(0, v) is the one worth putting
inside a loop, because its item-move count is Step 2 made measurable.What the counters at the bottom mean
A read is one value fetched out of a slot and a write is one value put into a slot. An item-move is one value shuffled sideways to make room or to close a gap. Those are the three kinds of work an array can be asked to do, and every command in the panel says which of them it costs.
Item-moves are the interesting one, because they are the cost nobody writes down. A single line
saying insertAt(0, 9) looks exactly as cheap as push(9), and the counter is
the only place the difference shows up.
insertAt(0, x) five times, one
after another. What will the item-moves counter say at the end?Linked lists
All of the array's pain comes from one demand: be contiguous. So what if we drop it?
Contiguous is a big word for a simple demand
Contiguous means touching, with nothing in between: slot 40, then 41, then 42, no gaps and no strangers. Step 1's address arithmetic only works because of that, since it assumes item 7 sits exactly seven item-widths past the start.
Let each item sit wherever it likes in memory, and have it carry a note saying where the next one is. That's a linked list. Inserting no longer shuffles anything: you just rewrite two notes. One box has to be the way in, though. A program keeps a single bookmark, called the head, holding the address of the first box, and everything else is reached by following notes from there. The last box is the tail. That is why the two operations a list is best at are the two at the head: they are the only two that do not involve walking.
What is actually written on the note
An address, the slot number from Step 1. Each item is stored as a small bundle: the value itself, plus the address where the next bundle lives. Programmers call that stored address a pointer, and the bundle a node.
The last node's pointer is left empty, which is how a program knows it has reached the end rather than wandering off into memory that belongs to someone else.
But look what you gave away. There's no arithmetic that finds item 7 any more, because the items aren't laid out in a pattern. To reach the seventh, you must start at the first and follow six notes. Try both below.
nxt on the right, where
the note saying "the next one lives here" is kept. The ∅ hanging off the far end is that note
left empty on the last box: nothing comes after it, and every walk along the chain stops when it meets
one.On paper linked lists look like a clear win for insertion. On real hardware they often lose anyway, because array items sit next to each other and arrive in the same cache line, while list nodes are scattered and each hop is a fresh trip to memory. Counting operations is not the same as measuring time, a theme that comes back in Step 14.
What a cache line is
Memory is not handed to the processor one slot at a time. It arrives in chunks, typically 64 bytes, and the chunk is kept in a small fast store called the cache. Reading one array item drags its neighbours along for free, so the next few reads never touch main memory at all.
List nodes are scattered, so each hop usually lands in a chunk nobody has fetched yet. Same number of steps on paper, very different waiting.
Stacks: last in, first out
Sometimes a restriction is a feature. A stack only lets you do two things: push, meaning put something on top, and pop, meaning take the top thing off. Looking at the top without removing it is a peek. No reaching into the middle. That's it.
That sounds crippling until you notice how many things in computing are naturally last-in-first-out: undo history, the back button, nested brackets, and most importantly function calls. When a function calls another function, the machine pushes a frame; when it returns, it pops. That's why it's called a call stack, and why infinite recursion produces a "stack overflow".
What a function is, if you have not met one
A function is a chunk of a program that has been given a name, so the rest of the program can
ask for it by that name instead of writing it out again. countdown(4) means "run the chunk
called countdown, and hand it the number 4 to work with". The number in the brackets is what you are
giving it, and different parts of a program call the same function with different numbers all day
long.
The part that matters here is what happens next. The moment one function asks for another, the first one stops mid-sentence and waits. It cannot finish until the one it asked for has finished, and that one may ask for a third, which asks for a fourth. Whatever started last has to finish first and the machine needs somewhere to park all that waiting. That somewhere is a stack.
What a frame is
When a function starts running it needs somewhere to keep its own things: the values it was handed, any names it makes up while working, and the address to jump back to when it finishes. That bundle is a frame.
Frames have to come off in the reverse of the order they went on, because the function that started last is always the one that finishes first. A stack is that rule made into a container.
I have not met recursion
Recursion is a function that calls itself on a smaller version of the same problem, like opening a box to find another box inside. Each call pushes a fresh frame, and the frames only start coming off once the innermost call finds a case small enough to answer outright.
Forget that stopping case and the calls never stop either. The frames pile up until the space set aside for them runs out, which is the overflow.
([{}]). Why is a stack exactly the
right tool?Queues and the ring
A queue is the other useful restriction: join at the back, leave from the front. First in, first out: a supermarket till, the line of documents waiting their turn at a printer, a list of jobs waiting for whoever is free to do them.
Build it naively on an array and Step 2 comes back to bite: taking from the front shifts everything. The fix is neat. Don't move the items. Move the ends. Keep a pointer to the front and one to the back, and when a pointer runs off the edge, let it wrap around to the start. The array becomes a ring. A block of slots set aside to hold things that are waiting is called a buffer, so this arrangement has a name of its own: a ring buffer. Nothing about it is actually round. The slots sit in the same straight row they always did, and only the two pointers travel. Those pointers are slot numbers here, rather than the memory addresses of Step 5.
Say that again with a clock face
A clock has twelve positions and no end. Two hours after eleven o'clock is one o'clock, because counting past the last position starts again at the first.
A ring buffer counts the same way over the slots of an array. The slots never move and the array is never actually bent into a circle. Only the two pointers travel, and they roll over instead of stopping.
What happens when the ring fills up
A ring holds a fixed number of slots, so something has to give when the back pointer catches the front. There are three usual answers: make the writer wait until a reader takes something out, throw away the oldest item to make room, or refuse the new item and report it.
Audio hardware picks the second, which is why a struggling machine drops sound rather than delaying it. Nothing later in the course depends on this.
Hash tables: a name becomes an address
Here is the problem that matters most in practice. You don't want item number 7. You want the item
called "gandalf". There is no arithmetic from a name to a slot… is there?
Two words before the recipe. The thing you look something up by, the name "gandalf"
itself, is called the key. The table you are looking in is an ordinary array of slots, except that each
slot is called a bucket. More than one key can end up sitting in the same bucket, which is where
the name comes from.
All the recipe has to do is turn any key at all into a bucket number.
There is, if you invent one. Take the letters of the key, mash them into a number by some fixed recipe, then wrap that number into the range of your table with a remainder. Now a name is an address, and looking it up is as fast as an array index.
def bucket_for(key, num_buckets):
h = 0
for ch in key:
h = (h * 31 + ord(ch)) % 1000000007 # mash the letters together
return h % num_buckets # wrap into the table
How to read that recipe if you have not seen code before
Read it as five instructions. Line one gives the recipe a name, bucket_for, and says it
needs two things handed to it: a key, and how many buckets the table has. Line two starts a running
total called h at zero. Line three says "do the next line once for every character in the key, calling
that character ch". Line four is the only arithmetic in the whole thing: multiply the running total by
31, add the number behind this character, and keep the remainder so the total cannot grow without
bound. Line five hands the answer back, folded into the range of the table.
The indentation is not decoration. In Python, the lines pushed further right are the ones inside the
loop, so line four is what gets repeated and line five happens once at the end. Everything after a
# is a note to human readers and is ignored.
I have not seen % before
The percent sign here is not percentages. It means remainder after dividing: 17 % 5 is 2, because 5 goes into 17 three times with 2 left over. Programmers call it modulo.
The useful part is the range. Whatever huge number you start with, taking the remainder by 8 always gives an answer from 0 to 7, so the result is always a slot that exists. That is what folds an unbounded number into a table of a fixed size.
What ord(ch) hands back
Every character has an agreed number behind it:"a" is 97,"b" is 98, a space is 32. Text is stored as those numbers, and ord is how a program asks for the one behind a character.
So the loop is not doing anything to letters as such. It is doing ordinary arithmetic on a handful of numbers that happen to spell a word.
That idea sits behind every dictionary, every Map, every database index lookup and
every cache you have ever used. Type a key below and watch it become an address.
When keys collide
The trick has an obvious hole. Squeeze unlimited possible keys into a finite number of buckets and sooner or later two keys land in the same one. Not rarely, either: with just 23 items and 365 buckets, there's a better-than-even chance of a clash. Collisions aren't an edge case; they're the normal operating condition.
How can 23 items in 365 buckets be a coin flip
Because a clash is about pairs, not about any one item. Twenty-three items make 253 different pairs, since each of the 23 can be paired with the other 22 and each pair gets counted twice. Every one of those 253 pairs is a fresh chance to match.
This is the birthday problem: 23 people in a room, and the odds that two share a birthday are slightly better than even. Skip the arithmetic if you like. The point that carries forward is only that collisions arrive far earlier than they feel like they should.
So a hash table isn't "keys go in buckets". It's "keys go in buckets, and here is the plan when two want the same one". There are two common plans: hang a little list off each bucket (chaining), or, if the bucket's taken, just walk forward to the next free one (open addressing).
The two plans, as a hotel
Chaining is a hotel where each room number can hold a bunk bed, and then a second bunk and a third. Everyone sleeps in the room the desk sent them to, and finding a guest means asking everyone in that one room.
Open addressing is a hotel where each room holds one guest. If your room is taken, you try the next door along until you find an empty one. Finding a guest means starting at their assigned room and walking until you meet them or hit an empty room.
How crowded a table has become has a name and a number. The load factor is the keys divided by the buckets: twelve keys in sixteen buckets is 12 ÷ 16 = 0.75. Below about 0.75, most buckets hold nothing or one thing, and a lookup is one piece of arithmetic and one comparison. Above it the chains lengthen quickly and every lookup starts paying for them. Watch that number in the lab below more closely than any of the others.
If every key collides, a hash table becomes one long list, and lookup goes from instant to walking the lot. Normally that needs bad luck, but an attacker who knows your hash function can craft keys that all collide on purpose and bring a server down. That's a real family of attacks, and it's why serious hash tables mix in a random seed at startup.
What a random seed is doing here
A seed is one number the program picks fresh each time it starts and stirs into the hash before anything else. The recipe is still public, but the answers it gives are different on every run.
So an outsider can no longer work out in advance which keys share a bucket, because the arrangement they would have to aim at did not exist until the program started.
The binary search tree
Hash tables are fast and forgetful: they find "gandalf" instantly but cannot tell you
which key comes next alphabetically, or list everything between "f" and "k". The scattering that makes
them fast destroys all order.
When you need order and speed, you need a tree. The rule for a binary search tree is one sentence: everything smaller goes left, everything bigger goes right. That's it. Apply it at every node and searching becomes a game of twenty questions: each comparison throws away half of what's left.
Root, node, leaf: the words for tree parts
A node here holds one value plus links to at most two others, called its left and right children. The single node at the top with nobody above it is the root. Nodes with no children at all are leaves.
Trees in computing are drawn upside down, root at the top and leaves at the bottom. The height is the longest walk from the root down to a leaf, and it is the number that decides how slow a search can get.
Why one comparison throws away half
Stand at the root holding the number 50, looking for 12. Because everything smaller went left, you know 12 cannot be anywhere on the right, and the whole right branch stops existing for you. You did not look at those items. You never will.
That is the same move as guessing a number between 1 and 100 by saying "is it under 50". One answer, half the possibilities gone.
What log₂ of a number means
It is a counting question: how many times do you halve this number before you reach 1? Halve 1000 and you get 500, 250, 125, 62, 31, 15, 7, 3, 1. Nine or ten halvings, so log₂(1000) is about 10.
Read the same thing backwards and it is doubling, which is the Step 3 arithmetic again: 2 doubled ten times passes 1000, and twenty times passes a million.
The tree that became a stick
Now break it. Insert 1, 2, 3, 4, 5, 6, 7 into an empty search tree, in that order, and follow the rule honestly: every new number is bigger than everything already there, so it goes right, every time.
You don't get a tree. You get a straight line, and searching a straight line means walking all of it. All the logarithmic speed is gone, and the input that destroyed it was sorted data, which is about the most common input there is.
What a rotation actually does
Take a node that is leaning right. Lift its right child up to become the new top, and hang the old top underneath on the left. Anything that was hanging off the middle gets re-attached to whichever side still keeps it in order.
Nothing is sorted or rebuilt, and no values change. Three links get rewritten, the smaller-left rule still holds everywhere, and the tree is one level shorter. AVL and red-black are the two best-known recipes for deciding when to rotate; both are named after their inventors or their drawings and the names tell you nothing. Later steps do not depend on knowing the details.
One new shape, made of two things you already have. O(log n) is Step 10's halving written in Step 3's notation: double the number of items and the cost goes up by one single step. Set against it, O(n) means double the items and you double the work. A binary search tree is O(log n) on average and O(n) in the worst case, and the worst case is triggered by ordinary sorted input rather than by anything exotic. Average-case performance is a promise about ordinary data. It is not a guarantee. Telling the two apart is most of the difference between a program that works on your own machine and one that still works once it is running for real. Your own data is small and tidy and you made it up. Real data is none of those things.
What ORDER BY id means
It is an instruction to a database: hand the records back sorted by their id number, smallest first. Perfectly ordinary, and most programs ask for it without thinking.
Which means the records arrive in exactly the order that turns a search tree into a stick. Two sensible habits, sorted records and a search tree, and together they undo each other.
ORDER BY id. What
happened?Heaps keep the smallest on top
Different question again: you don't want a particular item, and you don't want them all in order. You want the most urgent one, over and over, while new items keep arriving. That is the desk at a hospital emergency department, where the most badly hurt person is seen first however late they arrived. It is also how a computer picks which waiting job to run next. It is the engine inside Dijkstra's shortest-path algorithm. (An algorithm is a fixed recipe of steps that always produces the answer, the same way the hash recipe in Step 8 was one.)
Dijkstra's algorithm, in one line
It finds the shortest route through a network of places and roads by repeatedly stepping to the nearest place it has not visited yet, and writing down a better distance for that place's neighbours whenever it finds one.
The words "nearest one not visited yet, over and over" are the job a heap does. That is the only reason it turns up here, and nothing ahead depends on the route-finding itself.
Sorting everything would be wasteful: you only ever need the front. A heap keeps a much weaker promise, and that's the trick: every parent is smaller than its children. Nothing more. Siblings are in no particular order and the tree isn't sorted. But that one weak rule guarantees the smallest item is always at the very top. Keeping that rule true is all a heap ever does. Moving a new value up to its place is called sifting up, and pushing one back down is sifting down.
Smallest number, or most urgent job
A heap does not know what its numbers mean. You give every item a number and call it the priority, and the heap keeps the smallest one on top.
In a hospital that number might be how bad the injury is, counted so that 1 is worst. In a scheduler it might be the time a job is due. Turn the comparison around and the same structure keeps the largest on top instead, which is what people mean by a max-heap.
Why the children of i sit at 2i+1 and 2i+2
Write the tree into the array row by row, left to right, with no gaps. The root takes index 0. The next row takes 1 and 2, the row after takes 3, 4, 5, 6, and each row is twice the length of the one above it.
Count it through for the root: 2 times 0 plus 1 is 1, and plus 2 is 2, which is exactly the second row. For index 1: 3 and 4. For index 2: 5 and 6. Every parent lands on its own pair, so the links can be worked out instead of stored.
Graphs
Every structure so far imposes a shape: a row, a chain, a tree. But a lot of the world has no such shape. Friendships, roads, web links, dependencies between tasks, connections between neurons: these are just things and links between them, with no root and no order. That's a graph, and it's the most general structure there is.
The words: node, edge, neighbour
The things are nodes again, the same word as in the tree, and some people say vertices. Each link between two of them is an edge, and two nodes joined by an edge are neighbours.
A tree is a graph that has been told to behave: one root, and exactly one path between any two nodes. Drop those conditions and you get a graph, where a node can have any number of edges and paths can loop back on themselves.
The interesting question is how to store one. Two answers, with a sharp trade between them: a list of each node's neighbours, or a full grid of every possible pair marked yes or no.
Do links always point both ways
Not always. Friendship on most networks is mutual, and so is a two-way road, so those edges have no direction. A web link, a one-way street, or "this task must finish before that one" only works in one direction, and a graph with edges like that is called directed.
In the grid, an undirected graph makes a pattern that mirrors across the diagonal, because every yes appears twice. A directed one does not.
Reading a number like 10¹⁶
The small raised number counts the zeros: 10³ is 1000, and 10¹⁶ is a 1 with sixteen zeros after it. Each step up multiplies by ten, so 10⁹ is a thousand times bigger than 10⁶.
Multiplying two of them just adds the raised numbers. A hundred million is 10⁸, so a grid for a hundred million people needs 10⁸ times 10⁸, which is 10¹⁶ cells.
Race the six structures
You have built six structures. Everything anyone tells you about their speed is written in a table somewhere, in notation you're expected to take on trust. Let's not take it on trust.
All six are implemented below with a counter wired into every comparison, every hop and every move. Pick an operation, pick a size, and race them. The bars come from running the code, not from a table.
What the n in O(n) stands for
n is however many items the structure is holding at the moment: a thousand names, a million rows. Every big-O sentence is an answer to one question, which is what happens to the work as n grows.
So O(1) says the work ignores n, O(log n) says it creeps up by one step each time n doubles, and O(n) says the work keeps pace with n. In the race below, n is the size you pick.
It throws away constants. An O(1) operation that costs 500 units loses to an O(n) one costing 2 units until n passes 250. Big-O tells you which structure wins eventually, which matters enormously at scale and not at all for ten items. On small data, the array with its cache-friendly layout beats almost everything, whatever the table says.
Why the letter O, and what "asymptotically" means
The O is short for "order of", as in order of growth. It came from mathematics long before computing, as a way of saying which part of a formula ends up dominating once the numbers get large, and ignoring the rest.
Asymptotically means "once n is large enough", with no promise about how large that is. It is a claim about the far right of the graph below, which is why a structure can be asymptotically better and still lose on your actual data.
Which one, and why
The whole course collapses into one habit: don't ask which structure is best, ask which questions you need answered quickly. Every structure is fast at something and slow at something else, and the trade is never hidden: it's always visible in how the data is laid out.
The summary table
| Structure | By position | By key | Insert front | Insert end | Min | In order? |
|---|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(1)* | O(n) | no |
| Sorted array | O(1) | O(log n) | O(n) | O(n) | O(1) | yes |
| Linked list | O(n) | O(n) | O(1) | O(1)† | O(n) | no |
| Hash table | n/a | O(1)‡ | O(1)‡ | O(1)‡ | O(n) | no |
| Balanced tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | yes |
| Heap | n/a | O(n) | O(log n) | O(log n) | O(1) | no |
* amortized, thanks to doubling · † with a tail pointer · ‡ average case; O(n) if the keys collide badly
Six rows, and the lab above offers eight names, so three of them are missing here on purpose. A stack and a queue are not separate containers at all. Each one is an array or a list with a restriction bolted on, cheap at its one permitted end and no better than its underlying row anywhere else. A graph is not a container either. It is a shape made of things and links and the rows above are the containers you would reach for to store one.
A hash table has no front or back, so what do those columns mean
For a hash table or a heap there is no such thing as position: nothing is first and nothing is last, which is why the "by position" column says n/a for both. Their two insert columns are the same operation written twice, so the table can be read straight across.
Read a row as a shape rather than a ranking. The row tells you which questions this container answers cheaply, and the choice is about which of those questions your program keeps asking.
What a tail pointer is
A linked list normally keeps one bookmark, pointing at the first node. Adding at the end means following the chain the whole way to find the last node, which costs n hops.
A tail pointer is a second bookmark kept on the last node, updated whenever the end changes. With it, adding at the end is a couple of link rewrites and no walking, which is why that entry in the table carries a footnote.
You started with a row of numbered boxes and nothing else. Every structure since has been a different idea about how to arrange those boxes, and each one traded away something to get something else. None of them came from nowhere: people worked them out, and you have now worked them out too.
Where to go next
- Algorithms. Now that you have containers, learn the clever things to do with them: sorting, graph search, dynamic programming. Dijkstra's algorithm is a heap plus a graph plus one good idea.
- Inside a Database. B-trees are search trees reshaped for disks, where one node is one page and the cost model changes everything.
- Performance Engineering. Why the cache-friendly array so often beats the theoretically superior structure, and how to measure rather than guess.
State what must remain true after every operation
An abstract data type describes the operations and observations a caller receives. Its representation invariant describes legal internal states. A ring queue keeps its count between zero and capacity. A search tree keeps every left key smaller and every right key larger.
Test operation sequences against a small trusted model. After each push, pop, insert or delete, check the invariant and compare observations. This finds state bugs that one carefully chosen example never reaches.
Should invariant checks ship in production?
Cheap boundary checks often should. Expensive full scans can run in tests or sampled diagnostics. Never rely on a check to repair state it already found corrupt.
Make the unfinished work explicit
Depth-first search stores unfinished branches on a stack. Breadth-first search stores the frontier in a queue. Both need a visited set on a graph with cycles. Each vertex enters the worklist at most once, so traversal takes O(V + E) time for an adjacency-list graph.
An iterator exposes one item at a time without revealing the whole representation. Decide what happens if the collection changes during iteration: reject it, snapshot it or define which updates become visible.
Which traversal finds the fewest edges?
Breadth-first search does in an unweighted graph because it finishes distance d before distance d+1. Weighted shortest paths need other algorithms.
Track groups that merge
A disjoint-set forest supports find(x), which returns a group's representative, and
union(a,b), which merges two groups. It answers whether computers, pixels or map regions are
connected while edges are being added.
Union by size attaches the smaller tree under the larger. Path compression rewrites a find path directly to the root. Together they make long sequences extremely close to constant time.
Can union-find handle edge deletion?
Not directly. Its history only merges groups. Dynamic connectivity with deletions needs a different structure or offline reversal.
Combine structures when one cannot answer every operation
A least-recently-used cache needs lookup by key and order by recency. A hash table finds a key. A doubly linked list removes that exact node and moves it to the front. Each table entry stores the node reference, so get, put and eviction avoid scanning.
The invariant joins both structures: every table entry names exactly one list node, every list node appears in the table, and the tail is the least recently used item.
Why not use only an ordered list?
Moving a known node is cheap, but finding the node by key would scan. The table supplies the missing operation.
Count memory transfers, not only abstract operations
Processors move memory in cache lines. Consecutive array items often arrive together; linked nodes may require one wait per pointer. Big-O counts how work grows but hides these constants and transfers.
An array of structures keeps all fields of one record together. A structure of arrays keeps one field contiguous across records. The second layout can be better when a loop reads only that field.
Can the asymptotically worse structure win?
At relevant sizes, yes. Cache locality, allocation and branch prediction matter. Continue with Performance Engineering to measure them.
Share unchanged pieces across versions
A persistent update returns a new root while the old version remains usable. Copy only nodes on the changed path and share untouched subtrees. Immutability makes concurrent reading simpler, but reclamation must wait until no version can reach a shared node.
Ownership, reference counts, tracing and epoch schemes are different answers to that lifetime question. Pick one that matches the language and concurrency model.
Where is the full treatment?
Continue with Persistent Data Structures and Concurrent Data Structures.
Shape the structure around storage pages
When data exceeds memory, one random storage read costs far more than many comparisons. A B-tree node holds many keys so its height stays small and one node matches a page. Splits and merges preserve occupancy rules.
On disk, bytes need a versioned encoding, lengths, checksums and crash-safe update order. Write new pages before publishing the new root, or use a log so recovery can tell which update committed.
Where do databases continue this?
Balanced Search Trees develops B-trees; Tables, Trees and Transactions adds pages, logs and recovery.
Choose exact or approximate search deliberately
An exact index must return every matching key. Vector search asks for nearby points in a high-dimensional embedding. Approximate nearest-neighbour indexes skip much of the space and trade some recall for speed and memory. Measure recall against an exact reference set.
In 2026, hybrid retrieval commonly combines exact filters or lexical matches with vector candidates. Learned indexes can predict where to search, but need bounds and a correct fallback when the prediction misses. Data drift changes the workload and may invalidate yesterday's tuning.
Where is the full indexing path?
Text Indexes covers tries, suffix structures, embeddings, ANN and hybrid evaluation. Spatial Data Structures develops nearest-neighbour geometry.