Un tableau est un bloc contigu de mémoire contenant des éléments du même type, indexés à partir de 0. Puisque les éléments sont situés les uns à côté des autres, l'adresse de l'élément i est calculée directement comme base + i * elementSize, donnant un accès aléatoire en .
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
| Opération | Temps |
|---|---|
| Accès par index | O(1) |
| Recherche (non triée) | O(n) |
| Ajout (dynamique) | O(1) amorti |
| Insertion/suppression au début/milieu | O(n) |
Les tableaux sont la fondation de la plupart des autres structures — les chaînes de caractères, les tables de hachage, les tas et les listes dynamiques s'appuient tous sur eux.
Leur localité de cache fait souvent qu'un tableau « plus lent » en Big-O surpasse une structure basée sur des pointeurs « plus rapide » dans les repères réels.