Un array è un blocco contiguo di memoria che contiene elementi dello stesso tipo, indicizzati a partire da 0. Poiché gli elementi sono adiacenti l'uno all'altro, l'indirizzo dell'elemento i viene calcolato direttamente come base + i * elementSize, garantendo un accesso casuale in 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
| Operazione | Tempo |
|---|---|
| Accesso per indice | O(1) |
| Ricerca (non ordinato) | O(n) |
| Append (dinamico) | O(1) ammortizzato |
| Inserimento/eliminazione in testa/mezzo | O(n) |
Gli array sono il fondamento di quasi tutte le altre strutture — stringhe, hash table, heap e liste dinamiche si costruiscono tutti su di essi.
La loro località di cache spesso permette a un array con Big-O "più lento" di battere una struttura basata su puntatori "più veloce" nei benchmark reali.