Comment sont structurés les tableaux en programmation?

Les tableaux sont des collections ordonnées d'éléments du même type, stockés dans des cellules mémoire contiguës (séquentielles).

Caractéristiques principales:

• Indexation: L'accès aux éléments se fait par un indice commençant à 0. L'indice indique le décalage depuis le début du tableau.
• Taille: La taille du tableau (nombre d'éléments) est fixe lors de sa création dans les langages à typage statique ou peut changer dynamiquement dans les langages à typage dynamique (par exemple, en Swift Array).
• Type de données: Tous les éléments du tableau doivent avoir le même type de données.
• Contiguïté: Stocker les éléments dans des cellules mémoire contiguës garantit un accès rapide à n'importe quel élément via son indice.

Opérations:

• Accès par indice: O(1) - temps constant.
• Ajout/suppression à la fin: O(1) en moyenne pour les tableaux dynamiques (Swift Array).
• Ajout/suppression au début ou au milieu: O(n) - temps linéaire, car il peut être nécessaire de décaler les éléments.

Exemple en Swift:

// Création d'un tableau de chaînes
var names: [String] = ["Alice", "Bob", "Charlie"]

// Accès à un élément par indice
let first_name = names[0] // "Alice"

// Ajout d'un élément
names.append("David") // ["Alice", "Bob", "Charlie", "David"]

// Suppression d'un élément
names.remove(at: 1) // ["Alice", "Charlie", "David"]

// Itération sur le tableau
for name in names {
    print(name)
}

Structure interne (pour les tableaux dynamiques de type Swift Array):

Les tableaux dynamiques sont généralement implémentés sur un tampon mémoire statiquement alloué. Lorsqu'ils atteignent la capacité du tampon, un nouveau tampon plus grand est alloué et les anciens éléments sont copiés (réallocation). Cela garantit une complexité amortie de O(1) pour l'ajout à la fin.