ArrayList en images

Salut! La leçon d'aujourd'hui ArrayListsera à la fois plus facile et plus difficile que les leçons précédentes. Ce sera plus difficile car aujourd'hui nous allons regarder sous le capot ArrayListet étudier ce qui se passe lors de différentes opérations. Par contre, cette leçon n'aura presque pas de code. Ce sont surtout des photos et des explications. Eh bien, allons-y :) Comme vous le savez déjà, ArrayLista un tableau ordinaire à l'intérieur, qui agit comme un magasin de données. Dans la plupart des cas, nous ne spécifions pas la taille exacte de la liste. Mais le tableau interne doit avoir une certaine taille ! Et c'est ainsi. Sa taille par défaut est 10 .

public static void main(String[] args) {
   ArrayList<Car> cars = new ArrayList<>();
}

Voyons d'abord à quoi ressemble l'ajout de nouveaux éléments. La première chose à faire est de vérifier si le tableau interne dispose de suffisamment d'espace dans le tableau interne et si un élément supplémentaire conviendra. S'il y a de la place, le nouvel élément est ajouté à la fin de la liste. Quand nous disons "jusqu'à la fin", nous ne voulons pas dire la dernière position dans le tableau (ce serait bizarre). Nous entendons la position suivant le dernier élément courant. Son indice sera cars.size(). Notre liste est actuellement vide ( cars.size() == 0). En conséquence, le nouvel élément sera ajouté à la position 0.

ArrayList<Car> cars = new ArrayList<>();
Car ferrari = new Car("Ferrari 360 Spider");
cars.add(ferrari);

C'est assez clair. Que se passe-t-il si nous insérons au milieu, c'est-à-dire entre d'autres éléments ?

public static void main(String[] args) {
   ArrayList<Car> cars = new ArrayList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");
   Car ford = new Car("Ford Modneo");
  
   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
  
   cars.add(1, ford);// add ford to cell 1, which is already occupied
}

Encore une fois, il y a d'abord une vérification s'il y a suffisamment d'espace dans le tableau. S'il y a suffisamment d'espace, les éléments sont décalés vers la droite , en commençant par la position où nous insérons le nouvel élément. Nous insérons à la position 1. En d'autres termes, l'élément de la position 3 est copié à la position 4, l'élément 2 à la position 3 et l'élément 1 à la position 2. Ensuite, notre nouvel élément est inséré à sa place. L'élément précédent (bugatti) a déjà été copié à partir de là vers une nouvelle position. Voyons maintenant comment ce processus se produit s'il n'y a pas d'emplacement pour insérer de nouveaux éléments dans le tableau. Naturellement, il y a d'abord un contrôle pour voir s'il y a suffisamment d'espace. S'il n'y a pas assez de place, un nouveau tableau est créé à l'intérieur duArrayListdont la taille est la taille de l'ancien tableau multipliée par 1,5 plus 1 Dans notre cas, la taille du nouveau tableau sera de 16. Tous les éléments actuels y seront copiés immédiatement. L'ancien tableau sera supprimé par le ramasse-miettes et seul le nouveau tableau étendu restera. Il y a maintenant de la place pour un nouvel élément. Nous l'insérons à la position 3, qui est occupée. Maintenant, la procédure familière commence. Tous les éléments, en commençant par l'index 3, sont décalés d'une position vers la droite, et le nouvel élément est ajouté discrètement. Et l'insertion est faite ! Et nous en avons terminé avec l'insertion. Parlons maintenant de la suppression d'éléments . Vous vous souviendrez que nous avons rencontré un problème lorsque nous travaillions avec des tableaux : la suppression d'éléments crée des "trous" dans un tableau.à chaque suppression, et nous avons dû écrire notre propre code à chaque fois pour effectuer ce changement. ArrayList suit le même principe, mais il implémente déjà ce mécanisme. Voici à quoi cela ressemble : Et à la fin nous obtenons ce que nous voulons : L' lamboélément a été supprimé. Ici, nous avons supprimé un élément du milieu. En clair, supprimer un élément de la fin de la liste est plus rapide, puisque l'élément est simplement supprimé sans qu'il soit nécessaire de décaler tous les autres. Reparlons un instant des dimensions du tableau interne et de son agencement en mémoire. L'extension d'un tableau nécessite des ressources. Par conséquent, ne créez pas deArrayListavec la taille par défaut si vous êtes certain qu'il aura au moins 100 éléments. Le tableau interne devrait être étendu 6 fois au moment où vous insérez le 100e élément, et tous les éléments devraient être décalés à chaque fois.

• de 10 éléments à 16
• de 16 éléments à 25
• du 25 au 38
• de 38 à 58
• de 58 à 88
• de 88 à 133 (c'est-à-dire la taille de l'ancien tableau fois 1,5 plus 1)

Comme vous pouvez l'imaginer, c'est assez gourmand en ressources. Ainsi, si vous connaissez déjà (même approximativement) le nombre d'éléments requis, il est préférable de créer une liste avec un tableau d'une taille spécifique :

ArrayList<Car> cars = new ArrayList<>(100);

Désormais, la mémoire d'un tableau de 100 éléments sera allouée en une seule fois, ce qui rendra le tableau plus efficace (il n'aura pas besoin d'être étendu). Cette stratégie a aussi un revers. Lorsque vous supprimez des objets d'un ArrayList, la taille du tableau interne ne diminue pas automatiquement. Supposons que nous ayons un ArrayListavec un tableau interne complet de 88 éléments : Au fur et à mesure que le programme s'exécute, nous supprimons 77 éléments, il n'en reste donc que 11 : Avez-vous déjà deviné quel est le problème ? Vous l'avez compris, utilisation inefficace de la mémoire ! Nous n'utilisons ici que 11 positions, mais nous avons alloué de la mémoire pour 88 éléments. C'est 8 fois plus que ce dont nous avons besoin ! Dans ce cas, nous pouvons optimiser notre utilisation de la mémoire avec l'une des ArrayListméthodes spéciales de la classe :trimToSize(). Cette méthode "réduit" la longueur du tableau interne au nombre d'éléments qui y sont actuellement stockés. Maintenant, nous n'avons alloué que la quantité de mémoire dont nous avons besoin ! :)