Foundations · Module 3
Arrays and strings
The simplest structure and the fastest one: index arithmetic, growth, and how text is stored.
The array is the simplest data structure and, on real hardware, usually the fastest. This module takes it apart: the arithmetic that makes any element one step away, how a growable array keeps appends cheap, what inserting in the middle really costs, how text is stored as bytes, and the two-index techniques that solve many array problems in one pass without extra memory.
- 1Index arithmeticAn array index is an offset into a block of memory. The same arithmetic flattens grids, finds neighbors, wraps around the end and turns a position back into a row and column.13 min
- 2Dynamic arrays and growthA block of memory can't grow, so a growable array keeps spare capacity and moves to a bigger block when it fills. Growing by a factor, not a fixed amount, keeps appends O(1) on average.14 min
- 3Inserting and deleting in the middleAn array has no gaps, so inserting or deleting anywhere but the end shifts everything after that point. Knowing that cost, and the tricks that avoid it, decides how you use arrays.12 min
- 4Strings and encodingsA string is an array of numbers plus an agreement about what they mean. Unicode assigns the numbers, UTF-8 and UTF-16 turn them into bytes, and the choice decides what length and indexing mean.14 min
- 5Two pointers on arraysTwo indexes moving through one array can reverse it, test a palindrome, compact it or merge into it, in one pass and with O(1) extra memory.13 min