Des méthodes comme list java clear. Structures de données en images. Liste de tableaux. Estimation du temps d'exécution de l'opération d'ajout (valeur)
Dans la leçon précédente, nous avons abordé l'une des implémentations d'un tableau de longueur variable - l'implémentation utilisant la liste LinkedList
Pour utiliser ArrayList
Importer Java.util.ArrayList ;
Liste de tableaux
Exemple.
Liste de tableauxAvec cette ligne nous avons créé un objet de la classe ArrayList
Après avoir appliqué "list.add(5);" on obtient l'image suivante :
Si nous ajoutons un élément dix fois de suite et que nous voulons le faire la onzième fois, nous aurons un problème. Le problème est que notre tableau dans la liste est terminé et que nous n'avons nulle part où écrire des données. Il nous faut donc élargir le panel. Cela se produit automatiquement. Pour ce faire, un nouveau tableau de plus grande longueur est créé et les valeurs du tableau précédent y sont copiées. Il s’agit d’une opération assez coûteuse et prend environ O(N) itérations. Dans la classe ArrayList
Notez également qu'effectuer l'opération "list.remove(index);" ne réduira pas la longueur réelle du tableau dans la liste.
Tableau des temps de fonctionnement moyens pour ArrayList .
Considérons maintenant le temps d'exécution asymptotique des opérations sur ArrayList
Notez que les temps d'exécution add(value) et add(index, value) sont respectivement O(1) et O(size - index), bien que ces opérations exécutent O(size) dans le pire des cas. Montrons pourquoi le temps d'exécution moyen de l'opération add(value) est O(1).
Estimation du temps d’exécution de l’opération add(value).
Considérons d'abord l'option dans laquelle le tableau est augmenté d'un seul élément. Dans ce cas, lors de l'ajout d'un nouvel élément, nous devrons à chaque fois créer un nouveau tableau et y copier tous les éléments de l'ancien. Ainsi, le temps d'exécution de add(value) serait toujours (y compris en moyenne) égal à O(N). Même si nous élargissions notre tableau à chaque fois de k éléments, la durée d'exécution moyenne serait toujours de O(N). Vraiment. Chaque kième fois, l'opération est effectuée en O(N), et dans les autres cas en O(1). Si nous prenons la moyenne arithmétique, nous obtenons C * N, c'est-à-dire O(N).
Considérons maintenant un cas réel dans lequel le réseau est allongé d'une fois et demie à chaque fois. Remplissons un objet de type LinkedList
taille + (2/3) * taille + (2/3) 2 * taille + (2/3) 3 * taille + ... = taille / (1 - 2/3) = 3 * taille
Autrement dit, nous avons compris que l'opération add(value) size prend du temps C * size pour se terminer, ce qui signifie que le temps d'exécution de add(value) est O(1).
Méthodes supplémentaires dans ArrayList .
En plus des méthodes déjà apprises pour ArrayList
De plus, la longueur du tableau peut être définie lors de la construction d'un objet de la classe ArrayList
Liste de tableaux
Conclusion.
Présentation de la classe ArrayList
Dans la liste des tableaux
Étant donné que Java est un langage de programmation orienté objet, aucune des deux classes n'a un avantage significatif dans la lutte pour économiser la mémoire. Bien que formellement ArrayList gagne à cet égard
Liste liée
Le principal inconvénient d'ArrayList
Lors de la création de jeux tels que "Snake" ou " Bataille navale"c'était pratique à utiliser tableau bidimensionnel pour stocker les données du terrain de jeu. Mais utiliser uniquement des tableaux ne sera pas très pratique lors de la création du jeu Solitaire Solitaire. Dans les jeux "Snake" et "Battleship", les dimensions des terrains de jeu étaient taille fixe et n'a pas changé pendant le match. Un tableau est utile pour stocker, modifier et utiliser un ensemble fixe de valeurs. Dans le jeu Solitaire Solitaire, nous devrons stocker des ensembles de valeurs dont le nombre peut être augmenté ou diminué. Une liste de valeurs pouvant être implémentées en Java à l'aide de la classe ArrayList nous aidera avec ceci :
//Connectez la classe ArrayList
importer java.util.ArrayList ;
Examinons des exemples de travail avec une liste en utilisant une liste d'entiers comme exemple.
Tout d'abord, créons liste vide valeurs entières :
// Connecte la classe ArrayList
importer java.util.ArrayList ;
kosinka de classe publique (
public static void main (arguments de chaîne) (
//Créer une liste vide de valeurs entières
Liste de tableaux
Le type des éléments de la liste est indiqué entre les crochets angulaires
Liste de tableaux
Mais maintenant, nous allons considérer une liste d'entiers. Travailler avec des listes différents types les valeurs se produisent selon le même modèle.
Au départ la liste est vide :
Liste de tableaux
Ajoutons-y trois nouveaux éléments en utilisant la méthode add() :
// Crée une liste vide de valeurs entières
Liste de tableaux
//Ajoute le premier élément à la liste
//Ajoute un deuxième élément à la liste
//Ajoute un troisième élément à la liste
Les éléments sont ajoutés à la fin de la liste (voir Fig. 10).
Examinons maintenant les techniques de base pour travailler avec une liste :
// Récupère le nombre d'éléments dans la liste
// DANS dans ce cas– trois (voir Fig. 10)
int kol = lst.size();
// Récupération de la valeur d'un élément par numéro
// Dans ce cas – 100 (voir Fig. 10)
int val = lst.get(0);
// Suppression d'un élément de la liste par numéro
// Dans ce cas, celui du haut (voir Fig. 10)
// Supprime tous les éléments de la liste
En utilisant la méthode size(), vous pouvez déterminer le nombre d’éléments dans une liste.
La méthode get() vous permet d'obtenir la valeur de n'importe quel élément par numéro, la numérotation commence à zéro. La méthode Remove() supprime un élément de la liste par son numéro, la numérotation commence à zéro. Après la suppression d'un élément, la liste est automatiquement compressée. La méthode clear() vous permet de supprimer tous les éléments d’une liste en même temps. Tout comme dans un tableau, chaque élément de la liste possède son propre numéro. Le tout premier élément de la liste est numéroté zéro 0 et le tout dernier élément est numéroté size()-1. Ces méthodes de travail avec une liste seront suffisantes lors de la création du jeu Solitaire Solitaire. Sur le terrain de jeu, il y aura des cartes disposées en plusieurs piles. L'utilisateur transférera les cartes d'une pile à l'autre. Les cartes seront ajoutées à la fin de la pile de cartes. Par conséquent, toutes les méthodes énumérées ci-dessus seront suffisantes.
12 septembre 2011 à 18h19Structures de données en images. Liste de tableaux
- Java
Salutations, Habrapeople !
Il m'est venu à l'esprit d'écrire plusieurs articles sur la façon dont certaines structures de données sont implémentées en Java. J'espère que les articles seront utiles aux apprenants visuels (les images sont tout), aux visualiseurs Java débutants, ainsi qu'à ceux qui savent déjà écrire de nouvelles ArrayList(), mais qui n'ont aucune idée de ce qui se passe à l'intérieur.
Aujourd'hui, nous allons parler des ArrayLists
ArrayList - implémente l'interface List. Comme on le sait, dans Tableaux Java ont une longueur fixe et une fois le tableau créé, il ne peut ni s'agrandir ni se réduire. Une ArrayList peut changer de taille lors de l'exécution du programme, mais il n'est pas nécessaire de spécifier la dimension lors de la création de l'objet. Les éléments ArrayList peuvent être de n'importe quel type, y compris null.
Création d'un objet
Liste de tableauxL'objet liste nouvellement créé contient les propriétés elementData Et taille.
Stockage de valeur elementData n'est rien de plus qu'un tableau certain type(précisé en générique), dans notre cas Chaîne. Si un constructeur sans paramètres est appelé, alors par défaut un tableau de 10 éléments de type Object sera créé (avec un transtypage vers le type, bien sûr).
À l'intérieur d'une méthode ajouter(valeur) les choses suivantes se produisent :
AssurerCapacity(taille + 1);
2) un élément est ajouté à la fin (selon la valeur taille) tableau.
ElementData = élément ;
Toute la méthode assurerCapacité(minCapacité) Nous n'envisagerons pas, nous nous concentrerons uniquement sur quelques endroits intéressants. S'il n'y a pas assez d'espace dans la baie, la nouvelle capacité est calculée à l'aide de la formule (ancienneCapacité * 3) / 2 + 1. Le deuxième point concerne la copie d’éléments. Elle est réalisée à l'aide indigène méthode Système.arraycopy(), qui n'est pas écrit en Java.
// newCapacity - nouvelle valeur de capacité elementData = (E)new Object ; // oldData - stockage temporaire du tableau actuel avec les données System.arraycopy(oldData, 0, elementData, 0, size);
Vous trouverez ci-dessous une boucle qui ajoute 15 éléments un par un :
list.add("1");
...
Liste.add("10");
Lors de l'ajout du 11ème élément, la vérification montre qu'il n'y a pas d'espace dans le tableau. En conséquence, un nouveau tableau est créé et appelé Système.arraycopy().
Ajout au "milieu" de la liste
list.add(5, "100");L'ajout d'un élément à une position avec un index spécifique se déroule en trois étapes :
1) vérifie s'il y a suffisamment d'espace dans le tableau pour insérer un nouvel élément ;
EnsureCapacity(taille+1);
2) préparer une place pour un nouvel élément en utilisant Système.arraycopy();
System.arraycopy(elementData, index, elementData, index + 1, size - index);
3) la valeur de l'élément avec l'index spécifié est écrasée.
Comme vous pouvez le deviner, dans les cas où un élément est inséré à l'index et qu'il n'y a pas d'espace libre dans votre tableau, alors l'appel Système.arraycopy() cela se produira deux fois : d'abord dans assurerCapacité(), deuxième dans la méthode elle-même ajouter (index, valeur), ce qui affectera clairement la vitesse de toute l'opération d'ajout.
Dans les cas où il est nécessaire d'ajouter une autre collection à la liste d'origine, et même au « milieu », il vaut la peine d'utiliser la méthode addAll (index, collection). Et bien que cette méthode causera très probablement Système.arraycopy() trois fois, au final ce sera beaucoup plus rapide que l'addition élément par élément.
Supprimer des éléments
Vous pouvez supprimer des éléments de deux manières :- par indice supprimer (index)
- en valeur supprimer (valeur)
Supprimer un élément par index est assez simple
List.remove(5);
Tout d’abord, déterminez combien d’éléments doivent être copiés
Int numMoved = taille - index - 1 ;
puis copiez les éléments en utilisant Système.arraycopy()
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
réduisez la taille du tableau et oubliez le dernier élément
ElementData[--size] = null ; // Laisse gc faire son travail
Lors de la suppression par valeur, la boucle parcourt tous les éléments de la liste jusqu'à ce qu'une correspondance soit trouvée. Seul le premier élément trouvé sera supprimé.
Addendum 1 : Comme indiqué à juste titre
Qu’est-ce qu’ArrayList en Java ?
ArrayList est une structure de données qui peut être étirée pour accueillir des éléments supplémentaires en elle-même et réduite à une taille plus petite lorsque des éléments sont supprimés. Il s'agit d'une structure de données très importante, utile pour gérer le comportement dynamique des éléments.
Vous vous demandez comment ArrayList Java pourraitêtre utile, voir la conversation ci-dessous -
Regardez l’image suivante d’un homme étirant un élastique.
La longueur réelle de l'élastique est beaucoup plus petite, mais lorsqu'il est étiré, il peut s'étendre beaucoup plus que sa longueur réelle et peut être utilisé pour maintenir/lier des objets beaucoup plus gros avec lui.
Considérons maintenant l’image suivante, celle d’une simple corde, elle ne peut pas s’étirer et aura une longueur fixe.
Il peut croître au fur et à mesure des besoins pour accueillir les éléments qu'il doit stocker et lorsque des éléments sont supprimés, il peut revenir à une taille plus petite.
Donc, comme notre ami a un problème avec le tableau qu'il utilise ne peut pas être agrandi ou réduit, nous utiliserons ArrayList.
Les tableaux ressemblent à la corde montrée dans l'image ci-dessus ; ils auront une longueur fixe et ne pourront pas être agrandis ni réduits par rapport à la longueur d'origine.
Ainsi, notre élastique extensible ressemble beaucoup à la liste des tableaux alors que la corde peut être considérée comme le tableau.
Techniquement parlant, Java Array List est comme un tableau dynamique ou un tableau de longueur variable.
Voyons et comprenons l'extrait de code suivant qui vous aidera à travailler avec Array List.
Liste de tableaux
Méthodes ArrayList
ArrayList ajouter: Ceci est utilisé pour ajouter des éléments à la liste des tableaux. Si une ArrayList contient déjà des éléments, le nouvel élément est ajouté après le dernier élément, sauf si l'index est spécifié.
Ajouter (Objet o);
ArrayList supprimer: L'élément spécifié est supprimé de la liste et la taille est réduite en conséquence. Alternativement, vous pouvez également spécifier l'index de l'élément à supprimer.
Supprimer (Objet o);
Taille du tableau Java: Cela vous donnera le nombre d'éléments dans la liste des tableaux. Tout comme les tableaux, ici aussi le premier élément commence par l'index 0.
Taille Int();
ArrayList contient: Cette méthode retournera vrai si la liste contient l'élément spécifié.
Boolean contient (Objet o);
Exemple de liste de tableaux Java
importer java.util.ArrayList ; class Test_ArrayList ( public static void main(String args) ( //Création d'une ArrayList générique ArrayList arlTest = new ArrayList(); //Taille de arrayList System.out.println("Taille de ArrayList à la création : " + arlTest.size( )); //Ajoutons-y quelques éléments arlTest.add("D"); arlTest.add("K"); la taille après l'ajout d'éléments System.out.println("Taille de ArrayList après l'ajout d'éléments : " + arlTest.size()); //Afficher tout le contenu de ArrayList System.out.println("Liste de tous les éléments : " + arlTest ); //Supprimer certains éléments de la liste arlTest.remove("D"); out.println("Voir le contenu après avoir supprimé un élément : " + arlTest ; System.out.println("Voir le contenu après avoir supprimé un élément par index : " + arlTest //Vérifier la taille après avoir supprimé des éléments System.out.println); ("Taille de arrayList après suppression d'éléments : " + arlTest.size()) ; System.out.println("Liste de tous les éléments après suppression d'éléments : " + arlTest);//Vérifie si la liste contient "K" System.out.println(arlTest.contains("K"));
) )