Arrays and Dynamic Arrays

Level 1 introduced arrays as a programming convenience: one name, many slots. This lesson reopens the same structure at the machine level, because its performance profile, the exact set of operations that are cheap and the exact set that are expensive, all follows from a single physical fact: an array's elements sit next to each other in memory, in one contiguous block.

Contiguity buys the array its superpower. If the block starts at address A and every element occupies s bytes, then element i lives at address A plus i times s. That is one multiplication and one addition, the same tiny cost whether i is 3 or 3 million, and it is the entire secret behind O(1) access by index. No walking, no searching: the index is the address, after a little arithmetic. This model, the standard word-RAM account used by MIT's 6.006 and the Open Data Structures textbook, is worth internalizing because the next lesson's structure gives this superpower away and gets something else in return.

Picture a row of lockers built as one welded unit, numbered from 0. Told to open locker 41, you do not check lockers 0 through 40 first, you walk straight to it, because number 41 tells you exactly where it stands. Now feel the cost of that welded design: to squeeze a new locker between 3 and 4, you must shift every locker from 4 onward one position down the hallway. The convenience and the cost come from the same weld.

The price list

• Access by index: O(1). Address arithmetic, no traversal.
• Search for a value in unsorted data: O(n). Nothing about contiguity says where a value is, you scan.
• Insert or delete at index i: O(n). Every element after position i must shift by one to keep the block contiguous.
• Insert or delete at the front: the worst O(n) case, everything shifts.
• Append at the end: O(1) amortized, and earning that word amortized is the second half of this lesson.

The growth problem

A raw array has a fixed size, chosen when it is created, because the memory block behind it was allocated once. But the lists you actually use, a Python list, a JavaScript array, a Java ArrayList, a Lua table's array part, grow on demand. Under the hood, each is a dynamic array: a backing array plus a count of how many slots are used. Append while spare capacity remains and the cost is one write, O(1). Append when the backing array is full and the structure must allocate a bigger block and copy every existing element across, an O(n) operation.

So the size of the new block becomes the critical design decision. Grow by one slot each time and every single append triggers a full copy: appending n items costs 1 plus 2 plus 3 up to n copies, which is quadratic. The standard solution, analyzed in Open Data Structures' ArrayStack, is to grow geometrically: when full, allocate about double the capacity. Resizes then happen only at sizes 1, 2, 4, 8, 16, and the total copy work across n appends is at most 1 + 2 + 4 + ... which sums to less than 2n. Spread 2n copies across n appends and each append carries an average burden of about 2 copies: constant. That is amortized O(1): not a claim that every append is fast, one occasionally costs O(n), but a guarantee that any sequence of n appends costs O(n) in total. It is an accounting truth over sequences, not a probability.

Run the visualizer and watch the resize pattern: copies happen at sizes 1, 2, and 4, and the gaps between resizes double. Eight appends cost seven copies, safely under the 2n bound of sixteen. The doubling constant is not sacred, real implementations grow by factors like 1.5 or 2 with various refinements, but any fixed multiplicative factor delivers the amortized constant, while any fixed additive step does not. That distinction, multiplicative versus additive growth, is the entire content of the challenge below.

Why arrays dominate in practice

The asymptotic table undersells arrays in one respect: constants. Contiguous memory is exactly what modern CPU caches are built to accelerate, so scanning an array streams through the cache while pointer-chasing structures stall on every hop. This is why, even for workloads with some middle insertions, a dynamic array often beats a linked list in measured time despite the linked list's better insertion asymptotics. Big-O picks the winner at scale for a given operation mix; within a class, memory layout picks the winner on real silicon. Hold both truths at once and you will make better calls than either alone.

Arrays in shipped and protected code

Arrays are the shape protection work lives in. When an obfuscator encodes a program's strings, they land in one big constant array walked by a decoder loop. When a virtualizer compiles code for its custom machine, the bytecode ships as an array of numbers and the dispatch loop indexes into it, the O(1) access this lesson explained is what makes virtualization affordable at all. From the attacker's chair, the reverse-engineering level showed the same fact as a target: a large opaque array plus an indexed loop is a signpost reading decode me. Understanding the structure's mechanics is prerequisite to understanding both the defense and the attack built on it.

Contiguity gives arrays O(1) indexing through address arithmetic and costs them O(n) middle insertion through shifting. Dynamic arrays add growth by doubling, making appends amortized O(1): occasional expensive resizes averaged into constant cost per operation across any sequence. Geometric growth is what makes every language's built-in list usable.

Frequently asked questions