Tableaux et chaînes : les bases
DébutantLes structures les plus fondamentales, et la source de la majorité des problèmes d'entretien.
Un tableau stocke ses éléments dans des cases contiguës en mémoire : l'adresse de arr[i] se calcule directement, d'où l'accès en O(1).
Coût des opérations#
| Opération | Tableau dynamique |
|---|---|
| Accès par index | O(1) |
| Ajout / retrait en fin | O(1) amorti |
| Insertion / suppression au début ou au milieu | O(n) : il faut décaler les éléments |
| Recherche d'une valeur | O(n) (O(log n) si le tableau est trié) |
Les chaînes : attention à l'immutabilité#
En JavaScript, Python (et Java), les chaînes sont immuables : chaque concaténation crée une nouvelle chaîne. Concaténer dans une boucle peut donc coûter O(n²). On accumule dans un tableau, puis on assemble une seule fois.
// À éviter dans une boucle serrée : chaque += copie la chaîne
let s = "";
for (const c of chars) s += c;
// Préférer : accumuler puis assembler une seule fois, O(n)
const parts: string[] = [];
for (const c of chars) parts.push(c);
const joined = parts.join("");
Piège : un tableau non trié interdit la recherche binaire et les deux pointeurs. Avant de coder, demandez-vous toujours : « est-il trié ? » et « quelle est la taille maximale de
n? ». Ces deux réponses désignent la complexité visée.