7 min read

Why the layout decides the cost

Two ways to store the same five numbers, and what each one charges to reach an item.

You now have everything needed to see where costs come from. We are going to store the same five numbers, 7, 3, 11, 5 and 2, in two different ways, and then ask the same questions of each. Every structure in this course is a descendant of one of these two arrangements or a combination of them.

Arrangement one: keep them together

Put the five numbers in one unbroken run of memory, back to back, with nothing in between. The word for this is contiguous, which simply means touching, with no gaps. Each number takes four boxes, and the run starts at address 200. When we asked for the space we asked for room for six numbers and put five in, so there is one empty space on the end. That is deliberate and it matters later in the lesson.

index:      0       1       2       3       4       5
address:   200     204     208     212     216     220
         [  7  ] [  3  ] [ 11  ] [  5  ] [  2  ] [     ]

Five numbers kept together in one run, starting at address 200, with one space still empty on the end.

Suppose someone asks for the item at index 3. You do not need to look at any of the others. You work out where it must be: start at 200, go three items along, and each item is four boxes, so 200 plus 3 times 4 gives 212. Go to box 212. Done.

That is one multiplication and one addition, and then a single jump. It is exactly the same amount of work for index 3 as for index 3,000,000. The size of the collection never enters into it.

Arrangement two: let them scatter

Now store the same five numbers in five separate little places, wherever there happened to be room. On its own that would be useless, because you would have no way to find the next one. So alongside each number we also store the address of wherever the next one lives. The stored address is called a pointer, because it points at another place in memory.

start here: 200

  at 200:  [  7  | next is at 880 ]
  at 880:  [  3  | next is at 512 ]
  at 512:  [ 11  | next is at 344 ]
  at 344:  [  5  | next is at 700 ]
  at 700:  [  2  | nothing after   ]

The same five numbers scattered, each one holding the address of the next.

The order 7, 3, 11, 5, 2 is still there, but it lives entirely in the pointers. The addresses themselves are in no order at all, and it does not matter.

Now ask for the item at index 3 again. There is no calculation available, because the items are not evenly spaced and there is no starting point to count from. The only way is to begin at 200, read the pointer, go to 880, read the pointer, go to 512, read the pointer, go to 344. Three jumps to reach the fourth item, and reaching the thousandth item takes 999.

In the scattered arrangement, why can we not calculate where item 3 is, the way we did with the packed run?

Because the calculation depended on the items being evenly spaced from a known start. Item 3 sat at start plus 3 times the item size. When items are scattered, there is no fixed spacing and no relationship between an item's position in the sequence and its address, so the only way to find the fourth item is to follow the pointers from the beginning.