Pebellslearn by building
0%
RoadmapsMatrixCoursesSandboxSign in
Data Structures in Memory  ›  Lesson

Arrays — One Block of Memory

Array 12 minAn array stores its elements side by side in one block of memory, so the address of any element is the start address plus the index times the element size.

Arrays — One Block of Memory

A computer's memory is one enormous row of numbered boxes, each holding one byte. When you ask for scores[700], the machine does not count through 700 scores to get there. It works out exactly where the 701st score lives and goes straight to it. That trick is the whole reason arrays are the most common data structure in computing.

The rule

Address = start + index × size. One sum, any element.

An array reserves one unbroken block of memory and puts its elements side by side, all the same size. Three numbers are enough to find any element:

  • start: the address where the block begins,
  • index: which element you want, counting from 0,
  • size: how many bytes one element takes.

Say an array of 4-byte integers starts at address 1000:

address:  1000   1004   1008   1012   1016
index:      0      1      2      3      4
value:     42     17     99      8     63

Element 3 is at 1000 + 3 × 4 = 1012. This also explains why most languages count from 0: the index is really an offset, and the first element is zero steps from the start.

The same layout has a cost. Because elements must stay packed together in order, putting a new value at the front or in the middle means shifting everything after it one slot to the right. And if the block is full, a growing array (a Python list, a Java ArrayList) has to find a bigger block and copy everything across.

The shortcut

To find any element, don't picture walking along the array. Picture one jump: multiply, add, land. Then, for any change, ask "how many elements have to move?"

Finding and inserting in an 8-byte array at address 2000Step 1 of 4

  1. Find index 5

    5 × 8 = 40 bytes of offset, so the element is at 2000 + 40 = 2040. One calculation.

The trap: thinking a bigger index costs more to reach. Reading index 999999 is exactly as fast as index 1. Distance in the array costs nothing; only moving elements does.

Drills

Answer fast — trust the rule.

quick drill

An array of 4-byte integers starts at address 1000. Where is index 3?

quick drill

An array of 8-byte values starts at address 2000. Where is index 5?

quick drill

How does reading a[900000] compare with reading a[3] in a large array?

quick drill

An array holds 1000 elements with no gaps. Roughly how many elements move when you insert a new value at index 0?

Remember

  • An array is one packed block: address = start + index × size.
  • Reaching any index is one jump; the index being large costs nothing.
  • The trap is the middle and the front: inserting or deleting there shifts everything after it.

Practice — level up

0/1 solved

Write your answer, then compare it with a rubric and a model answer.

ExplainFast reads, slow inserts

An array of one million 4-byte integers starts at address 5000. Explain how the computer finds element 600000, why that takes the same time as finding element 2, and why inserting a new value at the very front is slow.