1. Comment ArrayListest structuré
ArrayListest la classe Java la plus couramment utilisée pour stocker des éléments. Alors, comment cela ArrayListfonctionne-t-il et pourquoi tout le monde l'aime-t-il autant ?
La structure de ArrayListest simple et ingénieuse. Chaque ArrayListobjet contient deux champs :
- Un tableau d'éléments
- Une
sizevariable, qui stocke le nombre d'éléments dans la liste
En interne, un ArrayListobjet contient un tableau des plus ordinaires ! Mais ce n'est pas tout. Il existe également une variable de taille , qui stocke la longueur de la liste. Voilà comment cela fonctionne:
Initialement, la longueur du tableau à l'intérieur de la liste est 10. Et la sizevariable est 0.
Si vous ajoutez un élément à la liste, il sera stocké dans la 0ème cellule du tableau et sizepassera à 1.
Si vous ajoutez un élément supplémentaire, il sera stocké dans la 1ère cellule, et sizeaugmentera à nouveau de 1 et deviendra égal à deux.
Si vous ajoutez un autre élément alors qu'il n'y a plus d'espace dans le tableau, voici ce qui se passe dans la add()méthode :
- Un nouveau tableau est créé qui est une fois et demie la longueur du précédent
- Tous les éléments de l'ancien tableau sont copiés dans le nouveau tableau.
- Dans l'
ArrayListobjet, une référence au nouveau tableau remplace la référence à l'ancien . - L'élément passé est enregistré dans la 10e cellule du nouveau tableau.
- La variable de taille augmente de 1 et sera désormais égale à 11
Quelque chose de similaire se produit lors de l'ajout (insertion) d'un élément au milieu de la liste. Les éléments existants sont décalés de 1 vers la droite et l'élément passé est écrit dans la cellule nouvellement libérée du tableau.
Nous allons maintenant examiner les scénarios les plus élémentaires impliquant des listes :
2. Ajouter un élément à unArrayList
Examinons ce qui se passe à l'intérieur de la liste lorsque des éléments y sont ajoutés. Immédiatement après la création d'un objet ArrayList, nous avons quelque chose comme ceci en mémoire :
Nous avons un ArrayListobjet qui contient deux champs (deux variables) : un conteneur (le datatableau) et le nombre d'éléments stockés ( size). La datavariable stocke une référence à un conteneur (tableau) pouvant stocker 10 éléments.
Si nous décidons d'ajouter le nombre 5 au tableau, nous obtenons l'image suivante :
Le tableau stocke maintenant l'élément 5, et size == 1.
Si quelqu'un appelle la size()méthode sur notre ArrayListobjet maintenant, la valeur de retour sera le nombre d'éléments stockés dans la liste : 1. Le nombre d'éléments dans la liste n'est pas le même que la capacité de stockage du tableau.
Ni la capacité de stockage actuelle ni le tableau lui-même ne seront jamais accessibles (visibles) en dehors de l' ArrayListobjet. Ce sont et seront toujours les ArrayListdonnées internes de .
Ajoutons 7 numéros supplémentaires à la liste : 10, 20, 30, 40, 50, 60, 70.
Maintenant, la mémoire ressemblera à ceci :
Si vous appelez la size()méthode maintenant, elle renverra le nombre 8, qui est le nouveau nombre d'éléments dans la liste. Cette valeur n'a rien à voir avec la taille du tableau interne.
Il y a une simplification excessive dans cette image.
La ArrayListclasse ne peut pas stocker de types primitifs, elle utilise donc le Integertype plutôt que int. Le conteneur ne stocke pas directement les valeurs {5, 10, 20, 30, 40, 50, 60, 70}, mais plutôt des références à Integerdes objets. Toutes les cellules vides du magasin de conteneurs null.
3. Augmenter la longueur d'une liste
Voyons ce qui se passe à l'intérieur d'une liste lorsqu'il n'y a plus de cellules vides dans son tableau interne.
Supposons que nous ayons une liste de 10 éléments :
Nous décidons d' y ajouter le nombre 100 . Voici ce qui se passe dans la add()méthode :
Étape 1 — Créez un nouveau tableau :
Étape 2 — Copiez tous les éléments de l'ancien tableau vers le nouveau :
Étape 3 — Remplacez l'ancien tableau (modifiez la référence au ArrayListtableau interne de l'objet) :
Étape 4 — Ajoutez le nouveau numéro, ce pour quoi nous avons travaillé si dur :
GO TO FULL VERSION