Arrays

Reading the millionth value of an array takes one step, but putting a new value at the front of the same array moves a million values.

What a data structure is

A program that keeps a list of names, a queue of print jobs or a table of prices has to store that data somewhere, and it has to answer questions about it: what is the third item, is this name in the list, which job is next? A data structure is a way of storing data together with the methods that answer those questions. MIT's 6.006 course separates two ideas here. The interface says which operations you can ask for, such as "get the item at position i" or "add an item at the end". The data structure is how those operations are actually carried out in memory. One interface can have several data structures behind it, and they can differ hugely in speed.

This course counts steps, as the algorithms course does, so that two structures can be compared without a stopwatch. In this unit a step is reading or writing one cell of memory. The lab below counts them for you.

One block of cells, side by side

An array stores its values in one unbroken block of memory, each value in a cell of the same size, numbered from 0. That layout is what makes arrays fast to read. If the block starts at address s and each cell takes c bytes, then a[i] lives at address s + i × c. The computer works that out with one multiplication and one addition and jumps straight there, whether i is 3 or 3,000,000. MIT's notes list "get at(i)" and "set at(i, x)" for an array as Θ(1), meaning the cost does not grow with the length.

The same layout makes changes in the middle slow. Suppose the array holds 7, 3, 9, 4, 6 and you want 1 at the front. There is no gap in front of 7, so every value has to move one cell to the right first, starting from the last one so nothing is overwritten. That is 5 moves and 1 write: 6 steps. Removing the front value is the mirror image: read it, then move the other 4 values one cell left. Inserting at position i in an array of n values costs n − i moves plus one write, so the front is the worst place and the end is the best.

When the block is full

A block of memory has a fixed size, so what happens when you add a value and every cell is taken? The array has to ask for a new, larger block and copy every value across before it can write the new one. In the lab, pushing onto the full block of 5 costs 5 copies and 1 write. If the array grew by just one cell each time, every push would copy everything, and n pushes would cost about n²/2 copies.

The fix described in MIT's notes is to grow by a lot at once, for example by doubling. Starting from capacity 1, the copies happen when the array holds 1, 2, 4, 8 and 16 values, so 17 pushes cost 1 + 2 + 4 + 8 + 16 = 31 copies in total, fewer than 2 per push. A single push can still be slow, but any long run of pushes averages out to a constant cost per push. This is called amortized Θ(1) time. A JavaScript array behaves this way from the outside: MDN describes arrays as resizable, and push and pop work at the end, which is the cheap end.

const a = [7, 3, 9, 4, 6];
console.log(a[3]);      // 4, one step
a.push(8);              // cheap: the end
a.unshift(1);           // every value moves one cell right
console.log(a.join(" ")); // 1 7 3 9 4 6 8