Comment la structure des index dans ArrayList est-elle implémentée?

Dans ArrayList, la structure des indices est implémentée via un tableau interne d’objets (Object[] elementData). Ce tableau sert de tableau dynamique, où chaque élément est accessible par indice en temps constant.

Lors de l’ajout d’éléments, ArrayList vérifie si l’espace dans le tableau est suffisant. Si ce n’est pas le cas, un nouveau tableau de taille plus grande (généralement 50% plus grand) est créé, et les éléments sont copiés dedans.

L’accès aux éléments par indice se fait directement via la référence au tableau:

E element = (E) elementData[index];

Ainsi, l’indice est simplement la position dans le tableau, ce qui assure une récupération et une mise à jour rapides des éléments. Cependant, insérer ou supprimer au milieu de la liste nécessite de décaler les éléments, ce qui prend un temps linéaire.