Um array é um bloco contíguo de memória que contém elementos do mesmo tipo, indexados a partir de 0. Como os elementos ficam um ao lado do outro, o endereço do elemento i é calculado diretamente como base + i * elementSize, oferecendo acesso aleatório O(1).
index: 0 1 2 3 4
+-----+-----+-----+-----+-----+
arr = | 10 | 20 | 30 | 40 | 50 |
+-----+-----+-----+-----+-----+
address: base +4 +8 +12 +16 (4-byte ints)
arr = [10, 20, 30, 40, 50]
x = arr[3] # O(1) — direct index math
arr.append(60) # amortized O(1) (dynamic array)
arr.insert(0, 5) # O(n) — shift every element right
arr.pop(0) # O(n) — shift every element left
| Operação | Tempo |
|---|---|
| Acesso por índice | O(1) |
| Busca (desordenada) | O(n) |
| Append (dinâmico) | O(1) amortizado |
| Inserção/exclusão na frente/meio | O(n) |
Arrays são a base de quase todas as outras estruturas — strings, tabelas hash, heaps e listas dinâmicas são todas construídas sobre eles.
Sua localidade de cache frequentemente faz um array com Big-O "mais lento" superar uma estrutura baseada em ponteiros "mais rápida" em benchmarks reais.
Uma biblioteca de perguntas de entrevista de TI com respostas detalhadas — de Júnior a Sênior.
Doar