Basics 0/97

Lesson 3 of 8

Arrays

Store values in numbered positions, read or change any of them directly, and visit them all in one pass.

5,206 words · 24 min read

Part 1 of 9 How an array is stored

How an array is stored in memory

One-line list operations can cost very different amounts. a[i] takes one step however long the list is. On a list of nn values, x in a takes up to nn steps, and a.pop(0) takes nn steps while a.pop() takes one. The differences all come from how a list is stored in memory.

Our example is the closing price of a stock on six days, numbered from 0:

day     0  1  2  3  4  5price   7  1  5  3  6  4

In a program this is the list prices = [7, 1, 5, 3, 6, 4], and prices[3] is 3, the price on day 3.

Definition

An array stores its values in slots of equal size, placed side by side in one block of memory. A slot's position in the block, counted from 0, is its index, so an array of nn values has indices 0 to n−1n - 1.

Find a slot from its index

Memory is a long row of numbered bytes, and the number of a byte is its address. Because the slots are equal in size and have no gaps between them, the program never has to search for slot ii. It computes the slot's address from the address where the block starts:

address of slot i=start+i×slot size\text{address of slot } i = \text{start} + i \times \text{slot size}
An array of 4-byte integers starting at address 1000.

In the figure the block starts at address 1000 and each slot takes 4 bytes, so slot 3 is at 1000+3×4=10121000 + 3 \times 4 = 1012. In an array of 100,000 prices, the last one would be at 1000+99,999×4=400,9961000 + 99{,}999 \times 4 = 400{,}996, found with the same multiplication and addition. So reading or replacing the value at an index takes the same few steps for every index and every length, which is constant time, O(1)O(1).

The figure draws 4-byte slots, the size of a C++ int. A Python list's slots are 8 bytes each, and each slot holds the address of a value stored elsewhere in memory, which is how one list can hold a short string beside a long one. The arithmetic is the same.

Finding a value is different. The formula turns an index into an address, but nothing turns the value 6 into an index. To learn whether any day closed at 6, the program compares the slots with 6 one at a time, and if the 6 is in the last slot or is missing, that takes nn comparisons, which is O(n)O(n).