What Is an Array?

A weather app that shows the week's temperatures needs seven numbers. It could use seven separate variables, monday, tuesday and so on, but then no loop could walk through them, and adding an eighth day would mean writing new code. An array puts all seven numbers under one name, temperatures, in numbered slots from 0 to 6.

How an array works

An array keeps its elements side by side in one block of memory, and every element takes the same number of bytes. That layout lets the computer find any element with one calculation:

address of element i = start address + i × element size

Suppose an array of 32-bit integers (4 bytes each) starts at memory address 1000. Element 0 is at 1000, element 1 at 1004, element 2 at 1008, and element 3 at 1012. Reaching element 3 or element 3,000,000 takes the same single step, which is why reading an array by index is called constant time, written O(1).

Python's array module stores raw numbers this way, so you can check the arithmetic:

from array import array

scores = array("i", [90, 75, 88, 62])
print(scores.itemsize, "bytes per element")
print(len(scores) * scores.itemsize, "bytes in total")

start = 1000  # pretend the array starts at address 1000
for index in range(len(scores)):
    address = start + index * scores.itemsize
    print("scores[" + str(index) + "] =", scores[index], "at address", address)

4 bytes per element
16 bytes in total
scores[0] = 90 at address 1000
scores[1] = 75 at address 1004
scores[2] = 88 at address 1008
scores[3] = 62 at address 1012

This formula also explains why most languages count from 0. The index is an offset: how many elements to skip from the start. The first element is 0 elements away from the start, so its index is 0, and the last element of an array of length n has index n − 1. A few languages, such as Lua, MATLAB, R and Fortran, start at 1 instead.

Using an array in Python

Most Python code uses the built-in list as its array. You create it with square brackets, read and change elements by index, and ask for its length with len():

temperatures = [18, 21, 25, 23, 19]

print(temperatures[0])   # first element
print(temperatures[2])   # third element
print(temperatures[-1])  # last element
print(len(temperatures))

temperatures[1] = 22     # change one element
temperatures.append(20)  # add one at the end
print(temperatures)

18
25
19
5
[18, 22, 25, 23, 19, 20]

A negative index counts from the end, so temperatures[-1] is the last element. That shortcut is Python's; C and Java have no negative indexes.

What array operations cost

The continuous layout makes some operations fast and others slow. The cost grows with n, the number of elements:

Inserting at the front is slow because every element has to move one slot to make room. Searching an unsorted array means a linear search through each element in turn, while a sorted array allows binary search, which halves the remaining range at every step.

Looping through an array

Arrays and loops go together: a loop visits each element in turn, which is called iteration. The same few lines handle an array of 5 elements or 5 million.

prices = [4.50, 12.00, 3.25, 8.75]

total = 0
for price in prices:
    total = total + price

print("Total:", total)
print("Most expensive:", max(prices))

Total: 28.5
Most expensive: 12.0

Arrays in other languages

In C, an array has a fixed size set when it is declared, and it holds raw values of one type. sizeof reports its size in bytes:

int scores[5] = {90, 75, 88, 62, 100};   /* 5 × 4 bytes = 20 bytes */

Java arrays also have a fixed length, and new elements start at a default value such as 0 for numbers. When you need a Java array that grows, you use ArrayList:

int[] scores = new int[5];   // five elements, all 0
scores[0] = 90;

JavaScript arrays grow and shrink freely and can mix types, as in [1, "two", true].

Arrays that grow, such as Python's list, Java's ArrayList and C++'s std::vector, are called dynamic arrays. They reserve extra space at the end. When that space runs out, they allocate a larger block, copy every element into it, and continue. The copies are rare enough that appending stays fast on average.

An array can also hold other arrays. grid[row][col] reads one cell of a two-dimensional array, the layout used for game boards, spreadsheets and images. The C guide to multidimensional arrays shows how they sit in memory.

Common mistakes

Off by one. An array of 3 elements has indexes 0, 1 and 2, so index 3 is past the end. Python stops with an error:

scores = [90, 75, 88]
print(scores[3])

IndexError: list index out of range

Java throws an ArrayIndexOutOfBoundsException, and JavaScript quietly returns undefined. C does no check at all: reading past the end is undefined behavior, which can return garbage or crash the program with a segmentation fault.

Copying by assignment. In Python, Java and JavaScript, b = a does not copy an array; both names refer to the same one, so changing b changes a. Use a.copy() in Python or [...a] in JavaScript for a real copy. The variable page explains why.

Where to go next

An array is only useful with a loop to walk through it, so read what iteration is next, and what a byte is for the unit behind the element sizes above. The Python lists guide covers slicing, sorting and list methods, and the linked list visualization shows the structure that trades fast indexing for fast inserts.