Tableaux
- Un tableau est une structure de données dans laquelle les éléments, tous de même type, occupent des positions contiguës en mémoire.
- Le nombre d’éléments qu’un tableau peut contenir est déterminé à la création d’un tableau.
| Type Python | Type | Opération | Exemple | Complexité |
|---|---|---|---|---|
| N’existe pas | Tableau | Accès à un élément | tab[i] |
$O(1)$ |
| Modification d’un élément | tab[i] = x |
$O(1)$ | ||
| Effacement d’un élément | retire(tab, i) |
$O(n)$ | ||
| Insertion d’un élément | insere(tab, x, i) |
$O(n)$ | ||
| Recherche d’un élément | est_dans(tab, x) |
$O(n)$ |
- La structure de données appelée « liste » dans le langage Python est implémentée à l’aide de tableaux dynamiques.
Remarque : Dans la suite de ce document, on va considérer que la liste Python tab, créé par l’instruction tab = [i for i in range(20)] est de longueur fixe. Elle se comporte alors comme un tableau.