Java ArrayList en images

Bonjour! La conférence d'aujourd'hui ArrayListsera, d'une part, plus simple et, d'autre part, plus difficile que les précédentes. C’est plus difficile, car aujourd’hui nous allons regarder « sous le capot » ArrayListet étudier ce qui se passe pendant les opérations. En revanche, il n'y aura presque pas de code dans ce cours – principalement des images et des explications. Alors c'est parti :) Comme vous le savez déjà, à l'intérieur ArrayListde 'a se trouve un tableau ordinaire, qui fait office de magasin de données. Dans la plupart des cas, nous ne précisons pas la taille exacte de la liste. Mais le tableau interne doit avoir une certaine taille ! C'est vrai. 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 d’un nouvel élément. Tout d'abord, une vérification est effectuée pour voir s'il y a suffisamment d'espace dans le tableau interne et si un élément supplémentaire peut y tenir. S'il y a de l'espace, le nouvel élément est ajouté à la fin de la liste. Quand on dit « jusqu’au bout », on ne parle pas de la dernière cellule du tableau (ce serait étrange). Il s'agit de la cellule à côté du dernier élément actuel. Son indice sera égal à cars.size(). Notre liste est actuellement vide ( cars.size() = 0). En conséquence, un nouvel élément sera ajouté à la cellule avec index 0.

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

Tout est clair ici. Que se passera-t-il si l'insertion s'effectue au milieu, c'est-à-dire entre plusieurs é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);//добавляем ford в ячейку 1, которая уже занята
}

Encore une fois, il vérifie d’abord 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 à partir de la cellule où l'on insère le nouvel élément. Nous collons dans la cellule d'index 1. Autrement dit, l'élément de la cellule 3 est copié dans la cellule 4, l'élément 2 dans la cellule 3, l'élément 1 dans la cellule 2. Après cela, notre nouvel élément est collé à sa place. L'élément précédent ( bugatti) a déjà été copié de là vers un nouvel emplacement. Voyons maintenant comment ce processus se produirait s'il n'y avait pas d'espace pour l'insertion dans le tableau. Bien entendu, tout d’abord, on vérifie s’il y a suffisamment d’espace. S'il s'avère qu'il n'y a pas assez d'espace, ArrayListun nouveau tableau de taille (taille OldArray * 1,5) + 1 est créé à l'intérieur de 'a. Dans notre cas, le nouveau tableau aura une taille de 16 cellules. 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 l'espace libre pour le nouvel élément. On le colle dans la cellule 3, qui est occupée. La procédure familière commence maintenant. Tous les éléments commençant à l'index 3 sont décalés d'une cellule vers la droite et un nouvel élément est ajouté discrètement. Et voilà, l'insertion est réussie ! Nous avons réglé l'insertion. Parlons maintenant de la suppression d'éléments . Comme vous vous en souvenez, lorsque nous travaillions avec des tableaux, nous avons rencontré un problème : lorsque nous les supprimions, des « trous » restaient dedans. La seule solution était de décaler les éléments vers la gauche à chaque fois qu'ils étaient supprimés, et il fallait écrire soi-même le code du décalage. ArrayListfonctionne sur le même principe, mais ce mécanisme y est déjà mis en œuvre automatiquement. Voici à quoi cela ressemble : Et au final, nous obtenons le résultat souhaité : L'élément lamboa été supprimé avec succès. Ici, nous avons effectué une suppression à partir du milieu. Il est clair que la suppression depuis la fin de la liste sera plus rapide, puisque l'élément souhaité est supprimé sans décaler tous les autres. Jetons un autre regard sur la taille du tableau interne et son stockage en mémoire. L'expansion d'un tableau est un processus qui nécessite une certaine quantité de ressources. Par conséquent, vous ne devez pas créer ArrayListavec la taille par défaut si vous savez avec certitude qu'elle contiendra au moins 100 éléments. Au moment où vous parviendrez à insérer le 100ème élément, le tableau interne s'agrandira 6 fois , transférant à chaque fois tous les éléments.

• de 10 éléments à 16
• de 16 éléments à 25
• du 25 au 38
• du 38 au 58
• de 58 à 88
• de 88 à 133 (selon la formule (taille de l'Ancien Tableau * 1,5) + 1)

Naturellement, cela coûte assez cher en termes de ressources. Par conséquent, si vous connaissez déjà un certain nombre (au moins approximatif) d'éléments stockés, il est préférable de créer immédiatement une liste avec un tableau d'une certaine taille :

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

Désormais, un tableau de 100 éléments sera immédiatement alloué en mémoire, ce qui sera plus efficace car les ressources ne seront pas gaspillées en expansion. Il y a aussi le revers de la médaille. Lorsque des objets sont supprimés du ArrayListtableau interne, la taille n'est pas automatiquement réduite. Par exemple, nous avons ArrayListun tableau interne de 88 éléments, qui est entièrement rempli : pendant le fonctionnement du programme, nous en supprimons 77 éléments, et il n'en reste que 11 : avez- vous déjà deviné quel est le problème ? Utilisation inefficace de la mémoire, bien sûr ! Nous n'utilisons que 11 cellules, alors que nous avons de la mémoire allouée pour 88 éléments, soit 8 fois plus que ce dont nous avons besoin ! Pour effectuer l'optimisation dans ce cas, vous pouvez utiliser une méthode de classe spéciale ArrayList- trimToSize(). Il « réduit » la longueur du tableau interne au nombre d’éléments actuellement stockés. Désormais, autant de mémoire est allouée que nécessaire ! :)