1.ArrayList implémente une structure de données basée sur des tableaux dynamiques et LinkedList implémente une structure de données basée sur des listes chaînées.
2. Pour obtenir et définir un accès aléatoire, ArrayList est meilleur que LinkedList car ArrayList peut être positionné de manière aléatoire, tandis que LinkedList doit déplacer le pointeur vers le nœud étape par étape. (Pensez en référence aux tableaux et aux listes chaînées)
3. Pour les opérations de création et de suppression d'ajout et de suppression, LinedList est plus avantageux. Il suffit de modifier le pointeur, tandis que ArrayList doit déplacer les données pour remplir l'espace de l'objet supprimé.
ArrayList et LinkedList sont deux classes de collection utilisées pour stocker une série de références d'objets. Par exemple, nous pouvons utiliser ArrayList pour stocker une série de String ou Integer. Alors, quelle est la différence de performances entre ArrayList et LinkedList ? Quand devez-vous utiliser ArrayList et quand devez-vous utiliser LinkedList ?
un. complexité temporelle
Le premier point clé est que l'implémentation interne d'ArrayList est basée sur un tableau d'objets de base. Par conséquent, lorsqu'elle utilise la méthode get pour accéder à n'importe quel élément de la liste (accès aléatoire), elle est plus rapide que LinkedList. La méthode get dans LinkedList vérifie d’un bout à l’autre de la liste dans l’ordre. Pour LinkedList, il n'existe pas de moyen plus rapide d'accéder à un élément spécifique de la liste.
Supposons que nous ayons une grande liste et que les éléments qu'elle contient ont été triés. Cette liste peut être de type ArrayList ou LinkedList. Nous effectuons maintenant une recherche binaire sur cette liste. La liste de comparaison est pour la vitesse de requête de ArrayList et LinkedList. voir le programme suivant :
Temps de LinkedList consommé : 2596
Ce résultat n'est pas fixe, mais fondamentalement, le temps d'ArrayList est nettement inférieur à celui de LinkedList. Par conséquent, LinkedList ne doit pas être utilisé dans ce cas. La méthode de recherche binaire utilise une stratégie d'accès aléatoire (randomaccess) et LinkedList ne prend pas en charge l'accès aléatoire rapide. Le temps consommé par l'accès aléatoire à une LinkedList est proportionnel à la taille de la liste. En conséquence, le temps consommé pour l'accès aléatoire dans ArrayList est corrigé.
Cela signifie-t-il qu'ArrayList fonctionne toujours mieux que LinkedList ? Ce n'est pas nécessairement vrai, dans certains cas, LinkedList fonctionne mieux qu'ArrayList, et certains algorithmes sont plus efficaces lorsqu'ils sont implémentés dans LinkedList. Par exemple, les performances sont meilleures lorsque vous utilisez la méthode Collections.reverse pour inverser une liste.
Regardez un tel exemple, si nous avons une liste et que nous souhaitons y effectuer un grand nombre d'opérations d'insertion et de suppression, dans ce cas, LinkedList est un meilleur choix. Prenons l'exemple extrême suivant, où nous insérons à plusieurs reprises un élément au début d'une liste :
À ce stade, ma sortie est : ArrayList prend : 2463
LinkedList prend : 15
Ceci est complètement opposé au résultat de l'exemple précédent lorsqu'un élément est ajouté au début de ArrayList, tous les éléments existants seront déplacés vers l'arrière, ce qui signifie la surcharge de déplacement et de copie des données. En revanche, l'ajout d'un élément au début d'une LinkedList attribue simplement un enregistrement à l'élément, puis ajuste les deux liens. Le coût d'ajout d'un élément au début d'une LinkedList est fixe, tandis que le coût d'ajout d'un élément au début d'une ArrayList est proportionnel à la taille de l'ArrayList.
deux. complexité de l'espace
Il existe une classe interne privée dans LinkedList, définie comme suit :
entrée de classe statique privée {
Élément d'objet ;
Entrée suivante ;
Entrée précédente ;
}
Chaque objet Entry fait référence à un élément de la liste, ainsi qu'à son élément précédent et à son élément suivant dans LinkedList. Un objet LinkedList avec 1000 éléments aura 1000 objets Entry liés entre eux, chaque objet correspondant à un élément de la liste. Dans ce cas, il y aura beaucoup de surcharge d'espace dans une structure LinkedList, car elle doit stocker les informations pertinentes de ces 1 000 objets Entity.
ArrayList utilise un tableau intégré pour stocker les éléments. La capacité de départ de ce tableau est de 10. Lorsque le tableau doit croître, la nouvelle capacité est obtenue selon la formule suivante : nouvelle capacité = (ancienne capacité*3)/2+. 1, c'est-à-dire que la capacité augmentera d'environ 50 % à chaque fois. Cela signifie que si vous avez un objet ArrayList avec un grand nombre d'éléments, vous vous retrouverez avec beaucoup d'espace perdu. Ce gaspillage est causé par le fonctionnement d'ArrayList. S'il n'y a pas assez d'espace pour stocker le nouvel élément, le tableau devra être réaffecté afin que le nouvel élément puisse être ajouté. La réaffectation de la baie entraînera une baisse drastique des performances. Si nous savons combien d’éléments une ArrayList aura, nous pouvons spécifier la capacité via le constructeur. Nous pouvons également utiliser la méthode trimToSize pour supprimer l'espace gaspillé après l'allocation de ArrayList.
trois. Résumer
ArrayList et LinkedList ont chacun leurs propres avantages et inconvénients en termes de performances, et chacun a sa propre application. De manière générale, cela peut être décrit comme suit :
Résumé des performances :
| - | opération ajouter() | opération delete() | opération d'insertion | opération de valeur d'index | opération de valeur d'itérateur |
|---|---|---|---|---|---|
| TableauListe/Vecteur/Pile | bien | Différence | Différence | Excellent | Excellent |
| Liste liée | bien | bien | bien | Différence | Excellent |
1. Pour ArrayList et LinkedList, le coût d'ajout d'un élément à la fin de la liste est fixe. Pour ArrayList, il ajoute principalement un élément au tableau interne, pointant vers l'élément ajouté, ce qui peut occasionnellement entraîner une réallocation du tableau ; pour LinkedList, cette surcharge est uniforme, allouant un objet Entry interne.
2. L'insertion ou la suppression d'un élément au milieu d'une ArrayList signifie que les éléments restants de la liste seront déplacés tandis que l'insertion ou la suppression d'un élément au milieu d'une LinkedList a un coût fixe.
3. LinkedList ne prend pas en charge un accès efficace aux éléments aléatoires.
4. Le gaspillage d'espace d'ArrayList se reflète principalement dans la réservation d'une certaine quantité d'espace à la fin de la liste, tandis que la consommation d'espace de LinkedList se reflète dans le fait que chaque élément de celle-ci doit consommer une quantité considérable d'espace.
Cela peut être dit comme ceci : lorsque l'opération consiste à ajouter des données après une colonne de données plutôt qu'au début ou au milieu, et que vous devez accéder aux éléments de manière aléatoire, l'utilisation d'ArrayList offrira de meilleures performances lorsque votre opération est devant ; une colonne de données Lorsque vous ajoutez ou supprimez des données au milieu et accédez aux éléments dans l'ordre, vous devez utiliser LinkedList.
La différence entre ArrayList et List en Java
Collection de listes
List hérite de l’interface Collection. La liste est une collection ordonnée. Les éléments de la liste peuvent être obtenus/supprimés/insérés en fonction de l'index (numéro de séquence : les informations de position de l'élément dans la collection).
Contrairement à la collection Set, List autorise les éléments en double. Pour les éléments d’objet e1 et e2 qui remplissent les conditions de e1.equals(e2), ils peuvent exister simultanément dans la collection List. Bien entendu, il existe également des classes d’implémentation List qui n’autorisent pas les éléments en double.
Dans le même temps, List fournit également une méthode listIterator(), qui renvoie un objet d'interface ListIterator. Par rapport à l'interface Iterator, ListIterator ajoute des méthodes pour ajouter, supprimer et définir des éléments, et peut également avancer ou reculer.
La relation entre Liste et Collection :
java.util.Collection[I]
+--java.util.List[I]
+--java.util.ArrayList [C]
+--java.util.LinkedList [C]
+--java.util.Vector [C]
+--java.util.Stack [C]
Les classes d'implémentation de l'interface List incluent principalement ArrayList, LinkedList, Vector, Stack, etc.
Relation père-fils.
List est une interface et ArrayList hérite de cette interface et l'implémente.
Lorsque je l'utilise, j'utilise généralement ArrayList. Je n'ai jamais utilisé List. Vous pouvez l'utiliser comme ceci : List list = new ArrayList();
Interface de collecte
Collection est l'interface de collection la plus basique. Une collection représente un ensemble d'objets, c'est-à-dire les éléments de la collection. Certaines collections autorisent des éléments identiques et d’autres non. Certains le font et d'autres non. Le SDK Java ne fournit pas de classes héritant directement de Collection. Les classes fournies par le SDK Java sont toutes des « sous-interfaces » qui héritent de Collection, telles que List et Set.
Toutes les classes qui implémentent l'interface Collection doivent fournir deux constructeurs standard : un constructeur sans paramètre pour créer une collection vide et un constructeur avec paramètre Collection pour créer une nouvelle collection. La collection d'entrée a les mêmes éléments. Ce dernier constructeur permet à l'utilisateur de copier une collection.
Comment parcourir chaque élément de Collection ? Quel que soit le type réel de Collection, il prend en charge une méthode iterator(), qui renvoie un itérateur pouvant être utilisé pour accéder à chaque élément de la Collection un par un. L'utilisation typique est la suivante :
Itérateur it = collection.iterator(); // Récupère un itérateur
while(it.hasNext()) {
Object obj = it.next(); // Récupère l'élément suivant
}
Les deux interfaces dérivées de l'interface Collection sont List et Set.
Interface de liste :
La liste est une collection ordonnée. Grâce à cette interface, vous pouvez contrôler avec précision la position d'insertion de chaque élément. Les utilisateurs peuvent accéder aux éléments de la liste à l'aide de l'index (la position de l'élément dans la liste, similaire à un indice de tableau), qui est similaire à un tableau Java.
Contrairement au Set mentionné ci-dessous, List autorise les mêmes éléments.
En plus de la méthode iterator() nécessaire à l'interface Collection, List fournit également une méthode listIterator(), qui renvoie une interface ListIterator. Par rapport à l'interface Iterator standard, ListIterator a quelques méthodes supplémentaires add() et autres, permettant des ajouts. Supprimez, définissez des éléments et avancez ou reculez.
Les classes courantes qui implémentent l'interface List sont LinkedList, ArrayList, Vector et Stack.
Classe LinkedList
LinkedList implémente l'interface List et autorise les éléments nuls. De plus, LinkedList fournit des méthodes supplémentaires d'obtention, de suppression et d'insertion en tête ou à la fin de LinkedList. Ces opérations permettent à LinkedList d'être utilisée comme pile, file d'attente ou deque.
Notez que LinkedList n'a pas de méthodes synchronisées. Si plusieurs threads accèdent à une liste en même temps, ils doivent implémenter eux-mêmes la synchronisation des accès. Une solution de contournement consiste à construire une liste synchronisée lors de la création de la liste :
Liste liste = Collections.synchronizedList(new LinkedList(...));
Classe ArrayList
ArrayList implémente des tableaux de taille variable. Il autorise tous les éléments, y compris null. ArrayList n'est pas synchronisé.
Le temps d’exécution des méthodes size, isEmpty, get et set est constant. Cependant, le coût de la méthode add est une constante amortie et l’ajout de n éléments nécessite un temps O(n). D'autres méthodes ont une durée d'exécution linéaire.
Chaque instance d'ArrayList a une capacité (Capacity), qui correspond à la taille du tableau utilisé pour stocker les éléments. Cette capacité augmente automatiquement à mesure que de nouveaux éléments sont ajoutés, mais l'algorithme de croissance n'est pas défini. Lorsqu'un grand nombre d'éléments doivent être insérés, la méthode EnsureCapacity peut être appelée pour augmenter la capacité de l'ArrayList avant l'insertion afin d'améliorer l'efficacité de l'insertion.
Comme LinkedList, ArrayList n'est pas non plus synchronisé.
Résumé : Si des opérations telles que des piles et des files d'attente sont impliquées, vous devez envisager d'utiliser List. Si vous devez insérer et supprimer rapidement des éléments, vous devez utiliser LinkedList. Si vous avez besoin d'un accès aléatoire rapide aux éléments, vous devez utiliser ArrayList.
Essayez de renvoyer l'interface plutôt que le type réel, par exemple en renvoyant List au lieu de ArrayList, de sorte que si vous devez remplacer ArrayList par LinkedList à l'avenir, le code client n'a pas besoin d'être modifié. C'est de la programmation pour l'abstraction.