Speaker note: Last week a box held one value, made and destroyed by malloc and free. This week two ideas grow out of that single box: many boxes side by side, reached by arithmetic — the array — and one box pointing at the next — the linked list.
Speaker note: Seventeen short animations carry the whole lecture; each appears once, exactly where its idea is introduced, and every single one gets a second look at its trickiest edge case.
Speaker note: Every term gets a full definition the first time it appears; this table just says where to find it again.
Speaker note: Open a terminal now if you want to run these live; every snippet on today's slides compiles and runs exactly as shown.
Speaker note: Everything today builds on exactly these five facts — nothing new about memory itself gets introduced this week, only new shapes built from it.
Speaker note: Every box on this map gets its own slides below, most with a short animation and a complete C/Java program.
Speaker note: Section 1 asks what it costs to change an array's contents, not just read them — and what to do when the array's size was guessed wrong.
Speaker note: Let the class guess before the next slide answers it: everything after the insertion point.
Speaker note: That O(1) index lookup is the array's whole appeal — and its whole cost shows up the moment something has to move.
Speaker note: CAP never changes in this first version; size is the only thing that moves, and only within 0..CAP.
Speaker note: Watch how many cells light up on a front insert versus an append — that difference is the whole lesson.
Speaker note: A full array rejects the insert outright rather than crash — that check has to come before any shifting starts.
Speaker note: The shift loop runs backward, from the end toward k — forward would overwrite values before they are copied.
Speaker note: This loop runs forward instead — the mirror image of insert's backward shift, and just as easy to get backward by mistake.
Speaker note: The exact same function costs anywhere from O(1) to O(n), purely depending on which index k the caller picks.
Speaker note: Let the class add it up before the next slide.
Speaker note: Ten shifts to place five values — inserting at the front is expensive precisely because it repeats the worst case every time.
Speaker note: This is exactly what Java's ArrayList and C++'s std::vector do under the hood — the same trick, industrial strength.
Speaker note: Watch the temporary row appear below the array each time it grows — that row is the copy, before it slides up to replace the old block.
Speaker note: Shrinking is optional and symmetric to growing — capacity halves once usage drops to a quarter full, to give memory back.
Speaker note: Every single existing value gets copied into the fresh block — that full copy is exactly where the O(n) cost of growing comes from.
Speaker note: The resize only happens when the block is already full — most calls skip straight to the one-line write at the end.
Speaker note: Amortized means averaged over a long run of operations — one append can be expensive, but the average never is.
Speaker note: Have the class count the doublings: 1, 2, 4, 8... before the next slide.
Speaker note: Doubling means the number of growths grows only as the logarithm of the final size — that is exactly why the total copying stays cheap.
Speaker note: Section 2 asks what a "two-dimensional" array actually looks like underneath, in memory that has only ever been one-dimensional.
Speaker note: There is no such thing as genuinely 2-D memory — every "2-D" array is really a 1-D array wearing a disguise.
Speaker note: Row-major versus column-major is purely a convention — nothing about "rows" or "columns" is more natural to memory than the other.
Speaker note: Two formulas, and every "2-D array" question this section asks comes down to picking the right one and applying it.
Speaker note: Watch the memory row below the grid — a row-major walk lands on consecutive memory cells, one step at a time.
Speaker note: The traversal order here fights the storage order — every step now jumps across memory instead of landing next door.
Speaker note: The outer loop over i and the inner loop over j exactly retrace the row-major formula, one visit per address in order.
Speaker note: The formula's cost never changes — what changes is how far apart consecutive visits land in real memory, which is what your CPU's cache actually feels.
Speaker note: Let the class apply the formula themselves before the next slide.
Speaker note: That one-step adjacency is exactly what "row-major" buys you, and exactly what a column-major walk would throw away.
Speaker note: Section 3 covers two array tricks that share one idea — moving values around using only O(1) extra space, never a second array.
Speaker note: The obvious approach — copy into a new array — is exactly the approach this section rules out.
Speaker note: This trick feels like magic the first time; watching it on the animation, one reversal at a time, is what makes it click.
Speaker note: Each reversal on its own looks wrong; only the third one, over the whole array, straightens everything back out.
Speaker note: Each reversal's result is kept as a new row below, so all three phases stay visible at once, side by side.
Speaker note: d=23 on 10 values still works, because d % n reduces it to 3 before a single reversal even begins.
Speaker note: This one helper function, called three times with three different ranges, is the entire rotation algorithm.
Speaker note: Three calls, three ranges — nothing else in this function does any work at all.
Speaker note: Three passes sounds like it should be three times slower, but three times O(n) is still just O(n).
Speaker note: This is the exact same two-pointer shape as a quicksort partition step — the same idea shows up again next semester.
Speaker note: Watch left and right walk toward each other, each skipping values that are already on the correct side.
Speaker note: The pointers still walk the whole array here, even though no swap is ever needed — the check itself still costs O(n).
Speaker note: Two inner while-loops skip past values already on the right side; only when both stop does an actual swap happen.
Speaker note: Every inner loop also checks left < right, or the two pointers could cross and read past each other.
Speaker note: Let the class think about what segregate actually compares.
Speaker note: Segregating and sorting are different jobs; this algorithm only ever asks "is it negative", never "which is bigger".
Speaker note: Section 4 asks what to do when a matrix is mostly zeros — a very common case in real scientific and graph computing.
Speaker note: A million ints is 4 MB just for one matrix that is 99.98% empty — the waste is not hypothetical.
Speaker note: Nobody photographs every empty parking space to prove it is empty — they just write down where the cars are.
Speaker note: Three numbers per nonzero cell replace an entire row of mostly zeros — the saving grows with how sparse the matrix is.
Speaker note: Watch how many cells get skipped silently — only the handful of nonzero ones ever produce a triplet row.
Speaker note: Every cell gets scanned and skipped — the triplet table stays completely empty, which is itself a valid, correct result.
Speaker note: The nested loops scan every cell regardless, but the if-check means only nonzero cells ever get written into out[].
Speaker note: The scan itself cannot be cheaper than the full matrix, but everything built from the result afterward benefits from the small output.
Speaker note: This is a genuinely clever trick — knowing in advance exactly where each entry belongs means never needing to sort at all.
Speaker note: Watch count[] fill first, then pos[] turn those counts into starting offsets, before a single output triplet is placed.
Speaker note: With every cell nonzero, fast transpose still works — it just has as many triplets to place as the matrix has cells.
Speaker note: pos[c] is the running total of every column before c — exactly where column c's triplets should start in the output.
Speaker note: pos[c]++ both reads the next free slot for column c and reserves it for the next triplet that lands there.
Speaker note: Skip the prefix-sum step and every triplet still gets placed somewhere — just not in the sorted order the algorithm promises.
Speaker note: Because both inputs are already sorted, addition never needs to search — it only ever needs to compare two current positions.
Speaker note: Watch pointers i and j advance independently, each stepping only through its own list, exactly like merging two sorted runs.
Speaker note: A cancelled cell is not written to the output at all — the result stays sparse, never picking up new zero entries.
Speaker note: Three cases only: a is earlier, b is earlier, or they land on the exact same cell and their values add together.
Speaker note: This whole approach depends on both lists already being sorted — feed it unsorted triplets and the merge silently gives the wrong answer.
Speaker note: Let the class work out the arithmetic before the next slide.
Speaker note: Keeping a zero-valued triplet around would quietly break the "only nonzero cells" promise the whole representation depends on.
Speaker note: Section 5 introduces the second major idea of the week — a structure where inserting never has to shift anything else.
Speaker note: Give the class a moment — the answer is exactly what the rest of today builds.
Speaker note: McCarthy was building a language for symbolic reasoning, not thinking about "data structures" as a subject — this idea simply turned out to be everywhere.
Speaker note: An array is a map you hold all at once; a linked list is a trail you can only walk one step at a time.
Speaker note: Every single linked-list program this week and next builds on exactly this five-line struct.
Speaker note: Lose head, and every node after it becomes unreachable — head is the single thread the whole list hangs from.
Speaker note: This self-reference trips up a lot of students the first time — the key is that a pointer is always the same small, fixed size, whatever it points at.
Speaker note: Dereferencing a NULL pointer is the single most common crash in every linked-list program this semester.
Speaker note: Let the class connect this back to the "inception" slide before the answer.
Speaker note: A pointer is always the same handful of bytes, no matter what it points at — that is precisely what breaks the circular dependency.
Speaker note: Section 6 builds the four operations every later list variant — doubly, circular, XOR, skip — reuses or extends.
Speaker note: The answer depends entirely on whether the list keeps a separate pointer to its tail, which this version does not.
Speaker note: "In order" is not a stylistic preference here — it is the difference between a working list and a severed one.
Speaker note: Watch insert_tail specifically — with no tail pointer, it has to walk past every existing node first.
Speaker note: This illustration never touches the real list — it exists purely to show why the write order in insert_after truly matters.
Speaker note: One malloc, one pointer write, one return — insert_head never even looks at the rest of the list.
Speaker note: Swap these two lines and prev->next already equals n by the time step one reads it — the new node ends up pointing at itself.
Speaker note: insert_after itself is O(1), but finding prev in the first place, via search, usually is not.
Speaker note: The bypass arrow is the entire trick: nothing points at cur any more, so it is simply unreachable, ready to be freed.
Speaker note: Watch prev and cur move together — prev always trails one step behind cur, ready to be relinked the moment cur is found.
Speaker note: Deleting the tail is not a separate case in this code at all — it falls naturally out of the same prev/cur scan.
Speaker note: The head case is handled separately here because head itself, not just some node's next field, has to change.
Speaker note: If prev is not updated in lockstep with cur, the bypass arrow ends up pointing from the wrong node entirely.
Speaker note: This is the single biggest thing a list gives up compared to an array — there is no way to jump straight to position k.
Speaker note: Watch the comparison counter climb — every node visited costs one comparison, whether or not it is the one being searched for.
Speaker note: An empty list means the for-loop's condition, cur != NULL, fails immediately — search returns -1 without ever comparing anything.
Speaker note: This entire function fits on one slide — nothing in today's lecture gets cut from it.
Speaker note: Keep this O(n) number in mind — it is the single biggest argument in the arrays-versus-lists table two sections from now.
Speaker note: Three pointers doing a coordinated dance, one node at a time, is the entire algorithm — no recursion, no extra memory.
Speaker note: Watch every arrow flip one at a time, always in the same order: save next, flip curr's arrow, advance both pointers.
Speaker note: Even the smallest non-trivial case runs through the exact same three-pointer dance, just for one iteration instead of many.
Speaker note: This whole function also fits on one slide, and it is worth reading it line by line, out loud, at least once.
Speaker note: In-place reversal, with no extra memory beyond three pointers, is the main reason this algorithm is worth learning by heart.
Speaker note: Let the class trace through what curr->next actually holds at each step before the answer.
Speaker note: This is the exact same "save before you overwrite" lesson as insert_after's step order, just showing up again in a different operation.
Speaker note: Section 7 adds a second pointer per node, in exchange for being able to walk in both directions.
Speaker note: The answer is almost too obvious once it's said out loud — but it changes how every operation has to be written.
Speaker note: The extra pointer is not free, though — it is one more field to keep correct on every single insert and delete.
Speaker note: Every pointer that used to skip over the insertion point now has a matching pointer coming back the other way — both need fixing.
Speaker note: Watch the two arrows on every node — next curving above the row, prev curving below — updated together, never just one.
Speaker note: Inserting after the current tail means the new node becomes the new tail — list->tail itself has to be updated, not just a next pointer.
Speaker note: Four pointer writes in total: the new node's own prev and next, the old next's prev (or list->tail), and cur's next.
Speaker note: cur->prev is read directly here — the singly version had to track a separate prev variable by hand while scanning.
Speaker note: The search cost never improves with a second pointer — only the relinking step, and the ability to walk backward, changes.
Speaker note: Point back to the delete_value code slide before the answer.
Speaker note: That stored prev field is the entire reason doubly lists exist — everything else follows from having it available at every node.
Speaker note: Section 8 removes NULL entirely — the list wraps around instead of ending — and uses that shape to solve a very old puzzle.
Speaker note: There is no obvious reason not to try this — and it turns out to be exactly what the Josephus problem needs.
Speaker note: Forgetting this is the classic circular-list bug: a loop written to stop at NULL simply never stops at all.
Speaker note: Keeping only tail, and deriving head from tail->next, is a small but deliberate design choice this program makes.
Speaker note: Watch the wrap-around arrow, drawn as a curve under the row, connecting the last node straight back to the first.
Speaker note: A one-node circular list points at itself; deleting that single node has to leave the list genuinely empty, tail set back to NULL.
Speaker note: The empty-list case is special precisely because there is no head->next relationship yet to preserve — the new node has to loop back to itself.
Speaker note: This mistake alone causes more infinite loops than any other bug in this week's material.
Speaker note: Whether the legend is exactly true or not, the elimination pattern it describes is precisely what this algorithm simulates.
Speaker note: Every elimination is just one bypass arrow, exactly like circular delete — the whole problem reduces to the operation just shown.
Speaker note: Watch the circle shrink by exactly one node per elimination, the wrap-around arrow redrawn each time.
Speaker note: With only one person in the circle, the elimination loop's remaining > 1 condition is false immediately — nobody is ever removed.
Speaker note: The inner for-loop counts exactly k-1 steps forward — the same bypass arrow from circular delete then removes whoever it lands on.
Speaker note: The simulation is what the animation shows step by step; the recurrence is a shortcut to just the final answer, no circle required.
Speaker note: Let the class walk through what k=1 actually means before the answer.
Speaker note: k=1 is the simplest possible case, and a good sanity check that the general algorithm still behaves the way plain intuition expects.
Speaker note: Section 9 is a memory-saving trick worth knowing about, but the mistakes slide near the end is the part that matters most.
Speaker note: It sounds impossible at first — you cannot literally store two addresses in the space of one — and yet there is a trick.
Speaker note: XOR-ing a value with itself always gives zero — that single fact is the entire trick behind this whole structure.
Speaker note: Watch each node's hex address and npx value on screen — the traversal literally computes the next address, live, at every step.
Speaker note: A single node in an empty list is both head and tail at once — its npx is just its one real neighbor, XOR'd with NULL.
Speaker note: xor_node is the one helper every other function in this program calls — it is where the trick actually lives.
Speaker note: prev starts as NULL, exactly the way an ordinary singly traversal starts — nothing else about the loop's shape has changed.
Speaker note: The time complexity does not actually improve over a doubly list — the entire benefit here is memory, not speed.
Speaker note: This is the single most important slide in this section — the trick is clever, but it is not something to actually ship.
Speaker note: Let the class connect this back to what a garbage collector actually has to do.
Speaker note: Java's simulation in the demo code works around exactly this by using array indices instead of real memory addresses.
Speaker note: Section 10 asks whether a linked list can ever get binary search's O(log n), and answers yes, with one extra idea.
Speaker note: The obstacle is that a list has no index at all, so "jump to the middle" is not even a meaningful operation — yet.
Speaker note: Pugh's own selling point was exactly this: the expected performance of a balanced tree, with far less code to get right.
Speaker note: More express lanes, more levels, keep shrinking the number of stops — this demo uses just two levels to keep it visible.
Speaker note: Every search starts at the highest level and works its way down, never going back up once it has dropped.
Speaker note: Watch the search start on the express lane, drop to the full list only once it overshoots, then take one final step.
Speaker note: With almost nothing on the express lane, most of the search still has to happen down at level 0.
Speaker note: The outer for-loop counts levels down from the top; the inner while-loop is the only place that ever moves cur to the right.
Speaker note: A real implementation flips a coin for each key's level at insert time — this demo fixes the levels in advance so every run is reproducible.
Speaker note: Let the class connect this back to what level 0 alone actually is.
Speaker note: This is worth sitting with: a skip list's speed is never guaranteed, only expected — its worst case is exactly a plain list.
Speaker note: Section 11 puts everything from today side by side, as one table, to make the trade-off explicit.
Speaker note: Only two rows actually differ — index access and front insertion — and they differ in opposite directions.
Speaker note: There is no universally "better" structure here — the right choice depends entirely on which operation the program actually does most.
Speaker note: Let the class think about which single operation a stack actually needs.
Speaker note: Next week's stacks and queues will make this choice concrete, with real implementations built on both.
Speaker note: Four ideas, and every one of them is really about the same question: what has to move, and how much, when the data changes.
Speaker note: Every one of these five list variants is still, underneath, just nodes and pointers — nothing here required any new kind of memory.
Speaker note: If a student remembers only one sentence from today, this is the one worth remembering.
Speaker note: These mirror the self-check quiz at the end of the written notes, one question per slide, with a shorter set here.
Speaker note: Ask, wait, then advance.
Speaker note: The same worst case from the very first mini-quiz of the day, just with a bigger array.
Speaker note: Recall the amortized-cost argument from section 1.
Speaker note: Amortized is an average over many operations, never a promise about any single one of them.
Speaker note: Recall the order-swap edge case from section 6.
Speaker note: A self-loop like that silently cuts off everything that used to follow prev in the list.
Speaker note: Recall the last mini-quiz of section 10.
Speaker note: A skip list's speed always depends on how many express levels actually exist above level 0.
Speaker note: Every stack and queue next week is built from exactly one of today's two structures, with the operations simply restricted to one end.
Speaker note: These are the same references listed at the end of the week's written notes.
Speaker note: The historical references — Pugh, McCarthy, Josephus — are what today's "short history" slides drew on.