O que é um array?

Um app de previsão do tempo que mostra as temperaturas da semana precisa de sete números. Ele poderia usar sete variáveis separadas, monday, tuesday e assim por diante, mas aí nenhum loop conseguiria percorrê-las, e acrescentar um oitavo dia significaria escrever código novo. Um array coloca os sete números sob um único nome, temperatures, em posições numeradas de 0 a 6.

Como um array funciona

Um array mantém os seus elementos lado a lado em um único bloco de memória, e todo elemento ocupa o mesmo número de bytes. Essa organização permite que o computador encontre qualquer elemento com um único cálculo:

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

Suponha um array de inteiros de 32 bits (4 bytes cada) que começa no endereço de memória 1000. O elemento 0 fica em 1000, o elemento 1 em 1004, o elemento 2 em 1008 e o elemento 3 em 1012. Chegar ao elemento 3 ou ao elemento 3.000.000 leva o mesmo único passo, e por isso ler um array pelo índice é chamado de tempo constante, escrito O(1).

O módulo array do Python guarda números brutos desse jeito, então você pode conferir a conta:

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

Essa fórmula também explica por que a maioria das linguagens conta a partir do 0. O índice é um deslocamento: quantos elementos pular a partir do início. O primeiro elemento está a 0 elementos do início, então o seu índice é 0, e o último elemento de um array de tamanho n tem índice n − 1. Algumas linguagens, como Lua, MATLAB, R e Fortran, começam em 1.

Usando um array em Python

A maior parte do código Python usa a list embutida como array. Você a cria com colchetes, lê e altera elementos pelo índice e pergunta o tamanho com 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]

Um índice negativo conta a partir do fim, então temperatures[-1] é o último elemento. Esse atalho é do Python; C e Java não têm índices negativos.

Quanto custam as operações em um array

A organização contínua deixa algumas operações rápidas e outras lentas. O custo cresce com n, o número de elementos:

Inserir no início é lento porque todo elemento precisa andar uma posição para abrir espaço. Procurar em um array não ordenado significa uma busca linear por cada elemento, um de cada vez, enquanto um array ordenado permite a busca binária, que corta pela metade o intervalo restante a cada passo.

Percorrendo um array

Arrays e loops andam juntos: um loop visita cada elemento por vez, o que se chama iteração. As mesmas poucas linhas lidam com um array de 5 elementos ou de 5 milhões.

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 em outras linguagens

Em C, um array tem um tamanho fixo definido na declaração e guarda valores brutos de um único tipo. sizeof informa o seu tamanho em bytes:

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

Os arrays do Java também têm tamanho fixo, e os elementos novos começam com um valor padrão, como 0 para números. Quando você precisa de um array em Java que cresça, usa ArrayList:

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

Os arrays do JavaScript crescem e diminuem livremente e podem misturar tipos, como em [1, "two", true].

Arrays que crescem, como a list do Python, o ArrayList do Java e o std::vector do C++, são chamados de arrays dinâmicos. Eles reservam espaço extra no fim. Quando esse espaço acaba, alocam um bloco maior, copiam todos os elementos para ele e continuam. As cópias são raras o bastante para que adicionar no fim continue rápido em média.

Um array também pode guardar outros arrays. grid[row][col] lê uma célula de um array bidimensional (uma matriz), a organização usada em tabuleiros de jogos, planilhas e imagens. O guia de arrays multidimensionais em C mostra como eles ficam na memória.

Erros comuns

Erro de um a mais (off by one). Um array de 3 elementos tem os índices 0, 1 e 2, então o índice 3 passa do fim. Python para com um erro:

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

IndexError: list index out of range

Java lança uma ArrayIndexOutOfBoundsException, e JavaScript retorna undefined sem avisar. C não faz verificação nenhuma: ler além do fim é comportamento indefinido, que pode devolver lixo ou derrubar o programa com um segmentation fault.

Copiar por atribuição. Em Python, Java e JavaScript, b = a não copia um array; os dois nomes se referem ao mesmo array, então alterar b altera a. Use a.copy() em Python ou [...a] em JavaScript para uma cópia de verdade. A página sobre variáveis explica o motivo.

Para onde ir agora

Um array só é útil com um loop para percorrê-lo, então leia o que é iteração em seguida, e o que é um byte para a unidade por trás dos tamanhos de elemento acima. O guia de listas em Python aborda fatiamento, ordenação e métodos de lista, e a visualização de lista ligada mostra a estrutura que troca o acesso rápido por índice por inserções rápidas.