Arrays: why the index is free
An array is one block of memory holding values of the same size, one after another with nothing in between. Everything arrays are good at and everything they are bad at comes from that one sentence.
Below is the same array drawn twice: the row of slots a programmer thinks in, and the addressed block the machine actually has. They are the same thing. The slot numbered 3 is not a label stuck on a value, it is a position in the block.
Press play on read. No searching happens, at any index. Then try insert and drag the index from one end to the other, and watch the price change.
1function read(a, i) {2 const size = 4 // bytes per element3 const at = a.base + i * size // where it is45 return memory[at] // go there, once6}
The array
fixed slots, and the values sitting in them
Reading index 5
- 31
- 14
- 58
- 62
- 9
- 27
- 41
- 75
8 elements
The same block, addressed
what the machine has: one run of bytes
- 0x7FFD0100[0]31
- 0x7FFD0104[1]14
- 0x7FFD0108[2]58
- 0x7FFD010C[3]62
- 0x7FFD0110[4]9
- 0x7FFD0114[5]27
- 0x7FFD0118[6]41
- 0x7FFD011C[7]75
Eight numbers in one block, each 4 bytes, one after another. Nothing here will be searched for.
The sum that makes reading free, the same property making insertion expensive, and why counting starts at zero.
The sum that makes it free
To find element 5, the machine does not look at elements 0 to 4. It works out where element 5 is:
address = start + index × sizeOne multiplication, one addition, then go there. The same two operations for the first element and for the millionth, which is what random access means: any position costs what any other position costs, and the word random is about arbitrary rather than unpredictable.
That sum needs two things to be true. Every element must be the same size, or multiplying by the index is meaningless. And they must be contiguous, with no gaps, or the count of elements stops matching the distance in bytes. Take either away and there is nothing left but searching.
The same property, sending the bill
Now switch to insert at index 0. To put a value at the front, every other element has to move up one slot first: 7 of them. Insert at the very end instead and 0 elements move.
The array cannot simply leave a gap and remember it, because a gap breaks the arithmetic above. Shifting is what keeps the block unbroken, and keeping the block unbroken is the only reason reading was free. It is one property, billed twice.
Removing is the same in reverse: take an element out of the middle and everything after it moves down to close the hole. Drag the index while watching the count and the shape comes out immediately. It is a straight line, worst at the front, free at the back.
Why counting starts at zero
The first element is at start + 0 × size, which is the start. The index is not a position in a queue, it is the distance from the beginning, measured in elements. Counting from one would put a subtraction in the middle of the most common operation in computing.
Growing an array that is already full
The block is a fixed size. When it fills up, the array cannot simply extend, because whatever sits immediately after it in memory belongs to something else. The only option is to find a larger block, copy everything across, and release the old one.
Which sounds ruinous, and is not, because of how much larger the new block is. Growing by a fixed number of slots means copying constantly. Doubling means each element is copied a handful of times over the array's whole life, and the average cost of an append comes out constant even though individual appends are occasionally enormous. Every growable array in every standard library does this, which is why appending is cheap and inserting at the front is not.
The reason arrays are faster than the counts suggest
Two operations that touch the same number of elements are not necessarily equally fast, and arrays win the comparison by more than the arithmetic says. Memory is not delivered a byte at a time: reading one address fetches the surrounding bytes as a block, on the assumption that whatever is next to something you wanted is something you will want.
For an array that assumption is exactly right, and walking one in order is close to the fastest thing a machine does. For a structure whose pieces are scattered, it is exactly wrong. This is the reason a shifting operation over a few thousand elements is often quicker in practice than a structure that claims to avoid the shift, and it is the single most common surprise when the theory meets a profiler.
What an array cannot do
It cannot change size cheaply. It cannot insert in the middle cheaply. It cannot be sparse without wasting the gaps. And every element must be the same size, so an array of variable-length things is really an array of addresses pointing at them, which gives up the contiguity that made it fast in the first place.
Each of those is a reason for one of the structures in the rest of this course, and that is the honest way to meet them: not as a catalogue, but as answers to specific complaints about this one.
The one-line summary worth carrying
Arrays trade the cost of changing shape for the cost of finding things. Where you know where something is, nothing beats them. Where things move around a lot, almost anything does.
Three questions
Pick an answer before you open one. Being wrong here is the useful part, and it is the whole reason to answer rather than read.
An array of 8 numbers starts at some address, with 4 bytes per element. Why does reading the sixth cost the same as reading the first?
Inserting a value at the front of an array of 8 moves 7 elements. Inserting at the very end moves 0. What explains the difference?
An array of 4-byte numbers starts at address 1000. At what address does element 7 begin?
Problems
Work them before opening the answers. Reading a solution feels like learning and is not.
Find the address
An array of 8-byte values starts at address 4000.
Where does element 5 begin, and where does it end?Show the answer →Hide the answer
Begins at 4040, ends at 4047.
4000 + 5 × 8 = 4040, and it occupies 8 bytes.Element 5 has five elements in front of it. Writing the sum out is worth doing once; after that it is the only thing you ever need to know about reading an array.
Count the moves
An array holds 100 elements.
How many move when you insert at index 0?
At index 99? At index 50?Show the answer →Hide the answer
100, then 0, then 50.It is a straight line from one end to the other. The average over all positions is about half the array, which is why insertion is called linear even though the best case is free.
Break the arithmetic
Suppose an array could hold values of different
sizes, packed one after another.
What stops working, and what would reading
element i cost?Show the answer →Hide the answer
The address sum stops working, because the
distance to element i is no longer i times
anything.
Reading element i would cost i steps: you would
have to walk the elements, adding up sizes.This is exactly what a structure of scattered pieces costs, and it is the trade the next lesson is about. Equal size is not a detail of arrays, it is half of the definition.
Why doubling
A growable array is full and must move to a
bigger block. One design adds 10 slots each time;
another doubles.
Appending a million values, roughly how many
element copies does each do?Show the answer →Hide the answer
Adding 10: about 50,000,000,000 copies.
Doubling: about 2,000,000 copies.Adding a fixed amount means copying the whole array every 10 appends, and the array keeps getting bigger, so the total is proportional to the square of the size. Doubling means each element is copied about twice on average over the whole life of the array.
Delete without shifting
You must remove elements from a large array often,
and you do not care what order the elements are in.
How do you make removal free?Show the answer →Hide the answer
Move the last element into the hole and shrink
the array by one.One write and one decrement, no shifting at all. It works only because order was not required, which is the point: the shifting is the price of keeping the order, not the price of removing. Ask what a structure actually has to guarantee and the cost usually comes down.
What gets asked, and what a good answer sounds like
Say these out loud rather than reading them. The gap between knowing something and being able to say it is the thing interviews measure.
+Why is array access constant time?
Because the position is computed rather than searched for: the start, plus the index times the element size. That needs the elements to be the same size and to sit next to each other with no gaps, and those two conditions are the entire reason it works.
+Then why is inserting in the middle slow?
The same two conditions. A gap cannot be left, so everything after the insertion point shifts up one slot to keep the block unbroken. It is the property that makes reading free, sending its bill. At the front that is the whole array; at the back it is nothing.
+What happens when a growable array runs out of room?
It allocates a larger block, copies everything into it, and releases the old one. Because the new block is usually double the size, each element gets copied only a couple of times across the array's whole life, so appending averages out to constant even though one append in a while is expensive.
+You need to delete often and order does not matter. What do you do?
Move the last element into the hole and shrink by one. No shifting at all. The shift was the cost of preserving order, not the cost of deleting, and noticing which guarantees you actually need is usually where the saving is.
+Why do indexes start at zero?
Because the index is the distance from the start measured in elements, not a position in a queue. The first element is zero elements along. Starting at one would put a subtraction inside the most frequently executed sum in computing.
Know someone stuck on this? Send it to them.
A classmate, a study group, someone learning this on their own at midnight. The link opens the lesson set up exactly as you have it, the same function and the same number, and runs from the first step so they watch the whole thing build rather than landing in the middle of it.
Before this one
Memory, addresses and pointers
Addresses have to mean something before a sum over them can. Start there if a box holding another box\u2019s number is new.
Start there →