Quand utiliser LinkedList sur ArrayList en Java ?
https://stackoverflow.com/questions/322715
-
11-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai toujours été du genre à utiliser simplement :
List<String> names = new ArrayList<>();
J'utilise l'interface comme nom de type pour portabilité, afin que lorsque je pose des questions comme celles-ci, je puisse retravailler mon code.
Quand devrait LinkedList être utilisé sur ArrayList et vice versa?
La solution
Résumé ArrayList avec ArrayDeque sont préférables dans beaucoup de cas d'utilisation plus nombreux que LinkedList. Si vous n'êtes pas sûr & Nbsp; & # 8212; commencez simplement par LinkedList<E>.
get(int index) et add(E element) sont deux implémentations différentes de l'interface de liste. add(int index, E element) l'implémente avec une liste doublement chaînée. index = 0 l'implémente avec un tableau de redimensionnement dynamique.
Comme pour les opérations de tableau lié et de tableau standard, les différentes méthodes auront des exécutions algorithmiques différentes.
Pour remove(int index)
-
Iterator.remove()est O (n) (avec n / 4 pas en moyenne) -
ListIterator.add(E element)est O (1) -
ArrayList<E>est O (n) (avec n / 4 pas en moyenne), mais O (1) lorsqueList< --- principal avantage deArrayLists - <=> est O (n) (avec n / 4 pas en moyenne)
- <=> est O (1) . < --- principal avantage de <=>
- <=> est O (1) C’est l’un des principaux avantages de <=>
Remarque: la plupart des opérations nécessitent n / 4 étapes en moyenne, constante nombre dans le meilleur des cas (exemple: index = 0) et n / 2 étapes dans le pire des cas (milieu de liste)
Pour <=>
- <=> est O (1) < --- principal avantage de <=>
- <=> est O (1) amorti, mais dans le pire des cas O (n) car le tableau doit être redimensionné et copié
- <=> est O (n) (avec n / 2 pas en moyenne)
- <=> est O (n) (avec n / 2 pas en moyenne)
- <=> est O (n) (avec n / 2 pas en moyenne)
- <=> est O (n) (avec n / 2 pas en moyenne)
Remarque: la plupart des opérations nécessitent n / 2 étapes en moyenne, constante nombre d'étapes dans le meilleur des cas (fin de liste), n étapes dans le pire des cas (début de la liste)
<=> autorise les insertions ou les suppressions à temps constant à l'aide d'itérateurs , mais uniquement l'accès séquentiel aux éléments. En d’autres termes, vous pouvez parcourir la liste en avant ou en arrière, mais trouver une position dans la liste prend du temps proportionnellement à la taille de la liste. Javadoc dit que & "Les opérations qui indexent dans la liste traverseront la liste depuis le début ou la fin, selon ce qui est le plus proche &"; . Ces méthodes sont donc O (n ) ( n / 4 étapes) en moyenne, bien que O (1) pour <=>.
<=> permettent en revanche un accès rapide en lecture aléatoire, ce qui vous permet de saisir n'importe quel élément en temps constant. Mais ajouter ou supprimer de n’importe où sauf la fin nécessite de déplacer tous ces derniers éléments, que ce soit pour faire une ouverture ou pour combler le vide. De même, si vous ajoutez plus d'éléments que la capacité du tableau sous-jacent, un nouveau tableau (1,5 fois la taille) est alloué et l'ancien tableau est copié dans le nouveau. Par conséquent, l'ajout à un <=> est O (n) dans le pire des cas, mais constant en moyenne.
Donc, en fonction des opérations que vous avez l'intention de faire, vous devez choisir les implémentations en conséquence. Itérer sur l'un ou l'autre type de liste est pratiquement aussi bon marché. (Itérer sur un <=> est techniquement plus rapide, mais à moins que vous ne fassiez quelque chose de très sensible à la performance, vous ne devriez pas vous inquiéter, ce sont deux constantes.
Les principaux avantages de l’utilisation de <=> se présentent lorsque vous réutilisez des itérateurs existants pour insérer et supprimer des éléments. Ces opérations peuvent ensuite être effectuées dans O (1) en modifiant la liste localement uniquement. Dans une liste de tableaux, le reste du tableau doit être déplacé (c.-à-d. Copié). De l’autre côté, rechercher dans un <=> signifie suivre les liens dans les O (n) ( n / 2 étapes) pour le pire des cas, alors que dans un <=> la position désirée peut être calculée mathématiquement et consultée dans O (1) .
Un autre avantage de l’utilisation de <=> se présente lorsque vous ajoutez ouretirer de l'en-tête de la liste, car ces opérations sont O (1) , alors qu'elles sont O (n) pour <=>. Notez que <=> peut être une bonne alternative à <=> pour ajouter et supprimer de la tête, mais ce n'est pas un <=>.
De même, si vous avez de grandes listes, gardez à l’esprit que l’utilisation de la mémoire est également différente. Chaque élément d'un <=> entraîne plus de temps système, car les pointeurs sur les éléments suivant et précédent sont également stockés. <=> ne pas avoir cette surcharge. Cependant, <=> utilise la mémoire allouée pour la capacité, que des éléments aient été ajoutés ou non.
La capacité initiale par défaut d'un <=> est plutôt petite (10 de Java 1.4 à 1.8). Mais comme l'implémentation sous-jacente est un tableau, vous devez le redimensionner si vous ajoutez beaucoup d'éléments. Pour éviter le coût élevé du redimensionnement lorsque vous savez que vous allez ajouter de nombreux éléments, construisez le <=> avec une capacité initiale supérieure.
Autres conseils
Jusqu'à présent, personne ne semble avoir traité de l'empreinte mémoire de chacune de ces listes, mis à part le consensus général selon lequel un LinkedList est & "beaucoup plus &"; qu’un ArrayList donc j’ai fait quelques calculs pour montrer à quel point les deux listes prennent pour N références nulles.
Comme les références sont 32 ou 64 bits (même lorsqu'elles sont nulles) sur leurs systèmes respectifs, j'ai inclus 4 jeux de données pour 32 et 64 bits LinkedLists et ArrayLists.
Remarque: Les tailles indiquées pour les lignes ArrayList object header + size integer + modCount integer + array reference + (array oject header + b * n) + MOD(array oject, 8) + MOD(ArrayList object, 8) == 8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8) + MOD(8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8), 8) correspondent aux listes tronquées - En pratique, la capacité de la matrice de sauvegarde dans un LinkedList object header + size integer + modCount integer + reference to header + reference to footer + (node object overhead + reference to previous element + reference to next element + reference to element) * n) + MOD(node object, 8) * n + MOD(LinkedList object, 8) == 8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n + MOD(8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n, 8) est généralement supérieure. que son nombre d'éléments actuel.
Remarque 2: (merci BeeOnRope) Comme CompressedOops est désormais défini par défaut à partir de JDK6 et supérieur, les valeurs ci-dessous pour les machines 64 bits correspondront à leurs performances 32 bits. homologues, à moins bien sûr que vous ne le désactiviez spécifiquement.
Le résultat montre clairement que <=> est beaucoup plus que <=>, en particulier avec un nombre d'éléments très élevé. Si la mémoire est un facteur, éloignez-vous de <=>.
Les formules que j'ai utilisées suivent, faites-moi savoir si j'ai fait quelque chose de mal et je vais le réparer. "b" correspond à 4 ou 8 pour les systèmes 32 ou 64 bits, et "n" correspond au nombre d'éléments. Notez que la raison des mods est que tous les objets en Java occuperont un espace multiple de 8 octets, qu’ils soient tous utilisés ou non.
ArrayList:
<=>
LinkedList:
<=>
ArrayList est ce que vous voulez. LinkedList est presque toujours un bug (de performance).
Pourquoi <=> est nul:
- Il utilise beaucoup de petits objets de mémoire et a donc un impact sur les performances tout au long du processus.
- Beaucoup de petits objets sont mauvais pour la cache-localité.
- Toute opération indexée nécessite une traversée, c’est-à-dire une performance de O (n). Cela n’est pas évident dans le code source, ce qui entraîne des algorithmes O (n) plus lents que si <=> était utilisé.
- Obtenir de bonnes performances est délicat.
- Même si les performances de Big-O sont identiques à celles de <=>, elles seront probablement beaucoup plus lentes de toute façon.
- C’est choquant de voir <=> dans le code source car c’est probablement le mauvais choix.
En tant que personne qui effectue l'ingénierie de la performance opérationnelle sur des services Web SOA à très grande échelle depuis environ une décennie, je préférerais le comportement de LinkedList à celui de ArrayList. Alors que le débit de LinkedList en état stable est pire et peut donc conduire à acheter plus de matériel, le comportement de ArrayList sous pression peut conduire les applications d'un cluster à étendre leurs baies de manière presque synchronicité et, pour les grandes tailles, à un manque de réactivité dans l'application et une panne, sous pression, ce qui est un comportement catastrophique.
De même, vous pouvez obtenir un meilleur débit dans une application grâce au collecteur de mémoire permanent par défaut, mais une fois que vous avez obtenu des applications java avec des piles de 10 Go, vous pouvez verrouiller l’application pendant 25 secondes lors d’un GC total, ce qui entraîne des délais d'attente et des échecs. dans les applications SOA et fait sauter vos accords de niveau de service si cela se produit trop souvent. Même si le collecteur CMS utilise plus de ressources et n'atteint pas le même débit brut, il s'agit d'un bien meilleur choix car il a une latence plus prévisible et plus réduite.
ArrayList n’est un meilleur choix en termes de performances que si vous entendez performances par performances, et que vous pouvez ignorer la latence. D'après mon expérience professionnelle, je ne peux pas ignorer la latence la plus défavorable.
Algorithm ArrayList LinkedList
seek front O(1) O(1)
seek back O(1) O(1)
seek to index O(1) O(N)
insert at front O(N) O(1)
insert at back O(1) O(1)
insert after an item O(N) O(1)
Les listes de tableaux sont bonnes pour l'écriture, les lectures uniques ou les ajouts, mais pas pour les ajouts / suppressions au début ou au milieu.
Oui, je sais, c’est une question ancienne, mais je vais ajouter mes deux sous:
LinkedList est presque toujours le mauvais choix en termes de performances. Il existe certains algorithmes très spécifiques dans lesquels une liste liée est requise, mais ceux-ci sont très rares et l'algorithme dépend généralement de la capacité de LinkedList d'insérer et de supprimer des éléments au milieu de la liste relativement rapidement, une fois que vous y avez navigué. avec un ListIterator.
Il existe un cas d'utilisation courant dans lequel LinkedList surpasse ArrayList: celui d'une file d'attente. Toutefois, si votre objectif est la performance, utilisez plutôt une ArrayBlockingQueue (au lieu de LinkedList) (si vous pouvez déterminer une limite supérieure de la taille de votre file d'attente à l'avance, et pouvez vous permettre d'allouer toute la mémoire à l'avance), ou cela Implémentation de CircularArrayList . (Oui, c'est à partir de 2001, vous aurez donc besoin de le générer, mais j'ai obtenu des ratios de performance comparables à ceux cités dans l'article récemment dans une machine virtuelle Java).
C'est une question d'efficacité. LinkedList est rapide pour ajouter et supprimer des éléments, mais lent pour accéder à un élément spécifique. ArrayList est rapide pour accéder à un élément spécifique mais peut être lent à ajouter à l'une ou l'autre extrémité, et particulièrement lent à supprimer au milieu.
Array vs ArrayList vs LinkedList vs Vector va plus en profondeur, tout comme Liste chaînée .
Correct ou incorrect: Veuillez exécuter le test localement et décider vous-même!
Modifier / Supprimer est plus rapide dans LinkedList que ArrayList.
Array, soutenu par <=>, qui doit être le double de sa taille, est pire dans les applications à grand volume.
Vous trouverez ci-dessous le résultat du test unitaire pour chaque opération. Le chronométrage est donné en nanosecondes.
Operation ArrayList LinkedList
AddAll (Insert) 101,16719 2623,29291
Add (Insert-Sequentially) 152,46840 966,62216
Add (insert-randomly) 36527 29193
remove (Delete) 20,56,9095 20,45,4904
contains (Search) 186,15,704 189,64,981
Voici le code:
import org.junit.Assert;
import org.junit.Test;
import java.util.*;
public class ArrayListVsLinkedList {
private static final int MAX = 500000;
String[] strings = maxArray();
////////////// ADD ALL ////////////////////////////////////////
@Test
public void arrayListAddAll() {
Watch watch = new Watch();
List<String> stringList = Arrays.asList(strings);
List<String> arrayList = new ArrayList<String>(MAX);
watch.start();
arrayList.addAll(stringList);
watch.totalTime("Array List addAll() = ");//101,16719 Nanoseconds
}
@Test
public void linkedListAddAll() throws Exception {
Watch watch = new Watch();
List<String> stringList = Arrays.asList(strings);
watch.start();
List<String> linkedList = new LinkedList<String>();
linkedList.addAll(stringList);
watch.totalTime("Linked List addAll() = "); //2623,29291 Nanoseconds
}
//Note: ArrayList is 26 time faster here than LinkedList for addAll()
///////////////// INSERT /////////////////////////////////////////////
@Test
public void arrayListAdd() {
Watch watch = new Watch();
List<String> arrayList = new ArrayList<String>(MAX);
watch.start();
for (String string : strings)
arrayList.add(string);
watch.totalTime("Array List add() = ");//152,46840 Nanoseconds
}
@Test
public void linkedListAdd() {
Watch watch = new Watch();
List<String> linkedList = new LinkedList<String>();
watch.start();
for (String string : strings)
linkedList.add(string);
watch.totalTime("Linked List add() = "); //966,62216 Nanoseconds
}
//Note: ArrayList is 9 times faster than LinkedList for add sequentially
/////////////////// INSERT IN BETWEEN ///////////////////////////////////////
@Test
public void arrayListInsertOne() {
Watch watch = new Watch();
List<String> stringList = Arrays.asList(strings);
List<String> arrayList = new ArrayList<String>(MAX + MAX / 10);
arrayList.addAll(stringList);
String insertString0 = getString(true, MAX / 2 + 10);
String insertString1 = getString(true, MAX / 2 + 20);
String insertString2 = getString(true, MAX / 2 + 30);
String insertString3 = getString(true, MAX / 2 + 40);
watch.start();
arrayList.add(insertString0);
arrayList.add(insertString1);
arrayList.add(insertString2);
arrayList.add(insertString3);
watch.totalTime("Array List add() = ");//36527
}
@Test
public void linkedListInsertOne() {
Watch watch = new Watch();
List<String> stringList = Arrays.asList(strings);
List<String> linkedList = new LinkedList<String>();
linkedList.addAll(stringList);
String insertString0 = getString(true, MAX / 2 + 10);
String insertString1 = getString(true, MAX / 2 + 20);
String insertString2 = getString(true, MAX / 2 + 30);
String insertString3 = getString(true, MAX / 2 + 40);
watch.start();
linkedList.add(insertString0);
linkedList.add(insertString1);
linkedList.add(insertString2);
linkedList.add(insertString3);
watch.totalTime("Linked List add = ");//29193
}
//Note: LinkedList is 3000 nanosecond faster than ArrayList for insert randomly.
////////////////// DELETE //////////////////////////////////////////////////////
@Test
public void arrayListRemove() throws Exception {
Watch watch = new Watch();
List<String> stringList = Arrays.asList(strings);
List<String> arrayList = new ArrayList<String>(MAX);
arrayList.addAll(stringList);
String searchString0 = getString(true, MAX / 2 + 10);
String searchString1 = getString(true, MAX / 2 + 20);
watch.start();
arrayList.remove(searchString0);
arrayList.remove(searchString1);
watch.totalTime("Array List remove() = ");//20,56,9095 Nanoseconds
}
@Test
public void linkedListRemove() throws Exception {
Watch watch = new Watch();
List<String> linkedList = new LinkedList<String>();
linkedList.addAll(Arrays.asList(strings));
String searchString0 = getString(true, MAX / 2 + 10);
String searchString1 = getString(true, MAX / 2 + 20);
watch.start();
linkedList.remove(searchString0);
linkedList.remove(searchString1);
watch.totalTime("Linked List remove = ");//20,45,4904 Nanoseconds
}
//Note: LinkedList is 10 millisecond faster than ArrayList while removing item.
///////////////////// SEARCH ///////////////////////////////////////////
@Test
public void arrayListSearch() throws Exception {
Watch watch = new Watch();
List<String> stringList = Arrays.asList(strings);
List<String> arrayList = new ArrayList<String>(MAX);
arrayList.addAll(stringList);
String searchString0 = getString(true, MAX / 2 + 10);
String searchString1 = getString(true, MAX / 2 + 20);
watch.start();
arrayList.contains(searchString0);
arrayList.contains(searchString1);
watch.totalTime("Array List addAll() time = ");//186,15,704
}
@Test
public void linkedListSearch() throws Exception {
Watch watch = new Watch();
List<String> linkedList = new LinkedList<String>();
linkedList.addAll(Arrays.asList(strings));
String searchString0 = getString(true, MAX / 2 + 10);
String searchString1 = getString(true, MAX / 2 + 20);
watch.start();
linkedList.contains(searchString0);
linkedList.contains(searchString1);
watch.totalTime("Linked List addAll() time = ");//189,64,981
}
//Note: Linked List is 500 Milliseconds faster than ArrayList
class Watch {
private long startTime;
private long endTime;
public void start() {
startTime = System.nanoTime();
}
private void stop() {
endTime = System.nanoTime();
}
public void totalTime(String s) {
stop();
System.out.println(s + (endTime - startTime));
}
}
private String[] maxArray() {
String[] strings = new String[MAX];
Boolean result = Boolean.TRUE;
for (int i = 0; i < MAX; i++) {
strings[i] = getString(result, i);
result = !result;
}
return strings;
}
private String getString(Boolean result, int i) {
return String.valueOf(result) + i + String.valueOf(!result);
}
}
ArrayList est essentiellement un tableau. LinkedList est implémenté en tant que liste à double liaison.
Le get est assez clair. O (1) pour add, car remove autorise l’accès aléatoire à l’aide d’index. O (n) pour <=>, car il doit d'abord trouver l'index. Remarque: il existe différentes versions de <=> et <=>.
<=> est plus rapide en ajout et en suppression, mais plus lent en get. En bref, <=> devrait être préféré si:
- il n'y a pas beaucoup d'accès aléatoire d'élément
- il existe un grand nombre d'opérations d'ajout / suppression
=== Liste de tableaux ===
- ajouter (E e)
- ajouter à la fin de ArrayList
- nécessite un coût de redimensionnement de la mémoire.
- O (n) pire, O (1) amorti
- add (index int, élément E)
- ajouter à une position d'index spécifique
- nécessite de décaler & amp; coût de redimensionnement de la mémoire possible
- O (n)
- remove (int index)
- supprime un élément spécifié
- nécessite de décaler & amp; coût de redimensionnement de la mémoire possible
- O (n)
- remove (Object o)
- supprime la première occurrence de l'élément spécifié de cette liste
- devez d'abord rechercher l'élément, puis décaler & amp; coût de redimensionnement de la mémoire possible
- O (n)
=== LinkedList ===
-
ajouter (E e)
- ajouter à la fin de la liste
- O (1)
-
add (index int, élément E)
- insérer à la position spécifiée
- devez d'abord trouver le poste
- O (n)
- remove ()
- supprime le premier élément de la liste
- O (1)
- remove (int index)
- supprimer un élément avec l'index spécifié
- besoin de trouver l'élément en premier
- O (n)
- remove (Object o)
- supprime la première occurrence de l'élément spécifié
- besoin de trouver l'élément en premier
- O (n)
Voici un chiffre tiré du programcreek.com (<=> et <=> sont le premier type, c’est-à-dire ajouter un élément à la fin de la liste et supprimer l’élément à la position spécifiée dans la liste.):
Joshua Bloch, l'auteur de LinkedList:
Quelqu'un utilise-t-il réellement LinkedList? Je l'ai écrit et je ne l'utilise jamais.
Lien: https://twitter.com/joshbloch/status/583813919019573248
Je suis désolé pour la réponse car elle n’a pas été aussi informative que les autres réponses, mais j’ai pensé que ce serait la solution la plus intéressante et la plus explicite.
ArrayList est accessible de manière aléatoire, tandis que LinkedList est vraiment bon marché pour développer et supprimer des éléments. Dans la plupart des cas, <=> c'est bien.
Sauf si vous avez créé de grandes listes et mesuré un goulet d'étranglement, vous n'aurez probablement jamais à vous soucier de la différence.
Si votre code contient add(0) et remove(0), utilisez une LinkedList et ses méthodes plus jolies addFirst() et removeFirst(). Sinon, utilisez ArrayList.
Et bien sûr, Gava , le ImmutableList est votre meilleur ami.
Je sais que ceci est un ancien post, mais honnêtement, je ne peux pas croire que personne ne mentionne que LinkedList implémente Deque. Il suffit de regarder les méthodes dans Queue (et ArrayDeque); si vous voulez une comparaison équitable, essayez d’exécuter <=> contre <=> et effectuez une comparaison fonctionnalité par fonctionnalité.
Voici la notation Big-O dans ArrayList et LinkedList ainsi que CopyOnWrite-ArrayList:
ArrayList
get O(1)
add O(1)
contains O(n)
next O(1)
remove O(n)
iterator.remove O(n)
LinkedList
get O(n)
add O(1)
contains O(n)
next O(1)
remove O(1)
iterator.remove O(1)
CopyOnWrite-ArrayList
get O(1)
add O(n)
contains O(n)
next O(1)
remove O(n)
iterator.remove O(n)
Sur cette base, vous devez décider quoi choisir. :)
TL; DR en raison de l'architecture informatique moderne, ArrayList sera nettement plus efficace dans presque tous les cas d'utilisation possibles - et doit donc être évité LinkedList sauf dans des cas exceptionnels et exceptionnels .
En théorie, LinkedList a un O (1) pour le add(E element)
L'ajout d'un élément au milieu d'une liste devrait également être très efficace.
La pratique est très différente, car LinkedList est une structure de données Cache Hostile . Point de vue des performances - il existe très peu de cas où Int pourrait être plus performant que le Cache-friendly Vector.
Voici les résultats d'un test de référence en insérant des éléments dans des emplacements aléatoires. Comme vous pouvez le constater, la liste de tableaux est beaucoup plus efficace, même si, théoriquement, chaque insertion au milieu de la liste nécessite & "Move &"; les n éléments ultérieurs du tableau (les valeurs basses conviennent mieux):
Travailler sur un matériel de dernière génération (caches plus grands et plus efficaces) - les résultats sont encore plus concluants:
LinkedList prend beaucoup plus de temps pour accomplir le même travail. source Code source
Il y a deux raisons principales à cela:
-
Principalement : les nœuds du <=> sont dispersés de manière aléatoire dans la mémoire. La RAM (& "; Random Access Memory &";) N'est pas vraiment aléatoire et des blocs de mémoire doivent être récupérés dans le cache. Cette opération prend du temps et, lorsque de tels extractions sont fréquentes, les pages de la mémoire cache doivent être remplacées à tout moment - & Gt; Cache misses - & Gt; Le cache n'est pas efficace. <=> Les éléments sont stockés dans une mémoire continue, ce qui correspond exactement à l’optimisation de l’architecture de la CPU moderne.
-
Secondaire <=> nécessaire pour conserver les pointeurs en arrière / en avant, ce qui représente 3 fois la consommation de mémoire par valeur stockée par rapport à <=>.
DynamicIntArray , btw, est une implémentation ArrayList personnalisée contenant <=> (type primitif) et non des objets - toutes les données sont donc réellement stockées de manière adjacente, d'où une efficacité accrue.
Un élément clé à retenir est que le coût de l'extraction d'un bloc de mémoire est plus important que le coût d'accès à une seule cellule de mémoire. C'est pourquoi le lecteur 1 Mo de mémoire séquentielle est jusqu'à 400 fois plus rapide que de lire cette quantité de données à partir de différents blocs de mémoire:
Latency Comparison Numbers (~2012)
----------------------------------
L1 cache reference 0.5 ns
Branch mispredict 5 ns
L2 cache reference 7 ns 14x L1 cache
Mutex lock/unlock 25 ns
Main memory reference 100 ns 20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy 3,000 ns 3 us
Send 1K bytes over 1 Gbps network 10,000 ns 10 us
Read 4K randomly from SSD* 150,000 ns 150 us ~1GB/sec SSD
Read 1 MB sequentially from memory 250,000 ns 250 us
Round trip within same datacenter 500,000 ns 500 us
Read 1 MB sequentially from SSD* 1,000,000 ns 1,000 us 1 ms ~1GB/sec SSD, 4X memory
Disk seek 10,000,000 ns 10,000 us 10 ms 20x datacenter roundtrip
Read 1 MB sequentially from disk 20,000,000 ns 20,000 us 20 ms 80x memory, 20X SSD
Send packet CA->Netherlands->CA 150,000,000 ns 150,000 us 150 ms
Source: Nombres de latence que chaque programmeur devrait connaître
Juste pour clarifier ce point, veuillez vérifier le point de repère de l’ajout d’éléments au début de la liste. C’est un cas d’utilisation où, en théorie, le <=> devrait vraiment briller, et <=> devrait présenter des résultats médiocres, voire pire:
Remarque: il s'agit d'un test d'évaluation de la bibliothèque C ++ Std, mais mon expérience précédente montrait que les résultats C ++ et Java étaient très similaires. code source
Copier un volume séquentiel de mémoire est une opération optimisée par les processeurs modernes: changer la théorie et rendre encore plus efficace <=> / <=> beaucoup plus efficace
Crédits: tous les points de repère affichés ici sont créésd par Kjell Hedstr & # 246; m . Vous trouverez encore plus de données sur son blog
.Comparons LinkedList et ArrayList avec w.r.t. paramètres ci-dessous:
1. Mise en œuvre
ArrayList est l'implémentation d'un tableau redimensionnable de l'interface de liste, tandis que
LinkedList est l'implémentation en liste à double lien de l'interface de liste.
2. Performance
-
get (int index) ou opération de recherche
ArrayList l'opération get (int index) s'exécute en temps constant, c'est-à-dire que O (1) while
LinkedList Le temps d'exécution de l'opération get (int index) est O (n).
La raison pour laquelle ArrayList est plus rapide que LinkedList est que ArrayList utilise un système basé sur un index pour ses éléments, tandis qu’il utilise en interne une structure de données de tableau.
LinkedList ne fournit pas d'accès basé sur l'index pour ses éléments, car il effectue une itération du début ou de la fin (selon l'option la plus proche) pour extraire le nœud à l'index d'élément spécifié.
-
opération insert () ou add (Object)
Les insertions dans LinkedList sont généralement rapides comparées à ArrayList. Dans LinkedList, l'ajout ou l'insertion est une opération O (1).
Dans ArrayList , si le tableau est plein, c'est-à-dire, dans le pire des cas, le redimensionnement et la copie des éléments dans le nouveau tableau entraînent des frais supplémentaires, ce qui rend l'exécution de l'opération d'ajout dans ArrayList O ( n), sinon c'est O (1).
-
opération remove (int)
L'opération de suppression dans LinkedList est généralement identique à ArrayList, c'est-à-dire O (n).
Dans LinkedList , il existe deux méthodes de suppression surchargées. on est remove () sans aucun paramètre qui supprime la tête de la liste et s'exécute à temps constant O (1). L'autre méthode remove surchargée dans LinkedList est remove (int) ou remove (Object), qui supprime l'objet ou l'int transmis en tant que paramètre. Cette méthode parcourt la liste LinkedList jusqu'à ce qu'elle trouve l'objet et la dissocie de la liste d'origine. Par conséquent, le temps d'exécution de cette méthode est O (n).
Alors que dans ArrayList , la méthode remove (int) implique la copie des éléments de l'ancien tableau vers le nouveau tableau mis à jour. Son exécution est donc O (n).
3. Itérateur inversé
LinkedList peut être itéré en sens inverse à l'aide de descendingIterator () avec
.il n'y a pas de descendingIterator () dans ArrayList , nous devons donc écrire notre propre code pour itérer sur ArrayList dans le sens inverse.
4. Capacité initiale
Si le constructeur n'est pas surchargé, ArrayList crée une liste vide de capacité initiale 10, tandis que
LinkedList construit uniquement la liste vide sans aucune capacité initiale.
5. Surcharge de la mémoire
La surcharge de mémoire dans LinkedList est supérieure à ArrayList puisqu'un nœud dans LinkedList doit conserver les adresses du nœud suivant et du nœud précédent. Alors que
Dans ArrayList , chaque index ne contient que l'objet réel (données).
En plus des autres arguments valables ci-dessus, notez que ArrayList implémente l'interface RandomAccess, tandis que LinkedList implémente Queue.
Ils abordent donc des problèmes légèrement différents, avec une efficacité et un comportement différents (voir la liste de leurs méthodes).
Une liste de tableaux est essentiellement un tableau avec des méthodes pour ajouter des éléments, etc. (et vous devriez utiliser une liste générique à la place). Il s'agit d'une collection d'éléments accessibles via un indexeur (par exemple [0]). Cela implique une progression d'un élément à l'autre.
Une liste chaînée spécifie la progression d’un élément à l’autre (élément a - > élément b). Vous pouvez obtenir le même effet avec une liste de tableaux, mais une liste chaînée indique absolument quel élément est censé suivre le précédent.
Cela dépend des opérations à effectuer sur la liste.
ArrayList est plus rapide pour accéder à une valeur indexée. C’est bien pire lors de l’insertion ou de la suppression d’objets.
Pour en savoir plus, lisez tout article traitant de la différence entre les tableaux et les listes chaînées.
J'utilise habituellement l'un sur l'autre en fonction de la complexité temporelle des opérations que j'effectuerais sur cette liste particulière.
|---------------------|---------------------|--------------------|------------|
| Operation | ArrayList | LinkedList | Winner |
|---------------------|---------------------|--------------------|------------|
| get(index) | O(1) | O(n) | ArrayList |
| | | n/4 steps in avg | |
|---------------------|---------------------|--------------------|------------|
| add(E) | O(1) | O(1) | LinkedList |
| |---------------------|--------------------| |
| | O(n) in worst case | | |
|---------------------|---------------------|--------------------|------------|
| add(index, E) | O(n) | O(n) | LinkedList |
| | n/2 steps | n/4 steps | |
| |---------------------|--------------------| |
| | | O(1) if index = 0 | |
|---------------------|---------------------|--------------------|------------|
| remove(index, E) | O(n) | O(n) | LinkedList |
| |---------------------|--------------------| |
| | n/2 steps | n/4 steps | |
|---------------------|---------------------|--------------------|------------|
| Iterator.remove() | O(n) | O(1) | LinkedList |
| ListIterator.add() | | | |
|---------------------|---------------------|--------------------|------------|
|--------------------------------------|-----------------------------------|
| ArrayList | LinkedList |
|--------------------------------------|-----------------------------------|
| Allows fast read access | Retrieving element takes O(n) |
|--------------------------------------|-----------------------------------|
| Adding an element require shifting | o(1) [but traversing takes time] |
| all the later elements | |
|--------------------------------------|-----------------------------------|
| To add more elements than capacity |
| new array need to be allocated |
|--------------------------------------|
Une caractéristique importante d’une liste chaînée (que je n’ai pas lue dans une autre réponse) est la concaténation de deux listes. Avec un tableau, c’est O (n) (+ surcharge de certaines réallocations); avec une liste chaînée, c’est seulement O (1) ou O (2); -)
Important : pour Java, ce n'est LinkedList pas vrai! Voir Existe-t-il une méthode de concat rapide pour la liste chaînée en Java?
J'ai lu les réponses, mais il existe un scénario dans lequel j'utilise toujours une liste LinkedList sur une liste ArrayList que je souhaite partager pour entendre les opinions:
Chaque fois que j'ai eu une méthode qui renvoie une liste de données obtenue à partir d'une base de données, j'utilise toujours une LinkedList.
Mon raisonnement était que, comme il est impossible de savoir exactement combien de résultats sont obtenus, la mémoire ne sera pas perdue (comme dans ArrayList avec la différence entre la capacité et le nombre réel d'éléments), et il n'y aurait pas de temps gaspillé en essayant de dupliquer la capacité.
En ce qui concerne ArrayList, je conviens qu'au moins, vous devriez toujours utiliser le constructeur avec la capacité initiale, afin de minimiser autant que possible la duplication des tableaux.
ArrayList et LinkedList ont leurs propres avantages et inconvénients.
ArrayList utilise une adresse mémoire contiguë par rapport à LinkedList qui utilise des pointeurs vers le noeud suivant. Ainsi, lorsque vous souhaitez rechercher un élément dans une liste de tableaux, cela est plus rapide que d'effectuer n itérations avec LinkedList.
D'un autre côté, l'insertion et la suppression dans une LinkedList sont beaucoup plus faciles car il vous suffit de changer les pointeurs, alors qu'une ArrayList implique l'utilisation de l'opération shift pour toute insertion ou suppression.
Si vous utilisez fréquemment des opérations de récupération dans votre application, utilisez une liste de tableaux. Si vous avez des insertions et des suppressions fréquentes, utilisez une LinkedList.
ArrayList et LinkedList les deux implémentent List interface et leurs méthodes et résultats sont presque identiques. Cependant, il existe peu de différences entre eux qui améliorent les uns par rapport aux autres.
ArrayList contre LinkedList
1) Search: get(int index) L’opération de recherche est assez rapide comparée à l’opération de recherche O(1). O(n) dans Reason: donne les performances de Deletion: alors que Inserts Performance: performances sont Memory Overhead:.
iterator listIterator maintient un système basé sur un index pour ses éléments, car il utilise implicitement la structure de données de tableau, ce qui accélère la recherche d'un élément dans la liste. De l’autre côté, fail-fast implémente une liste doublement chaînée qui nécessite la traversée de tous les éléments pour rechercher un élément.
2) iterator’s throw l'opération de suppression donne ConcurrentModificationException des performances tandis que (O(1)) donne des performances variables: ArrayList(O(n)) dans le pire des cas (lors de la suppression du premier élément) et get method dans le meilleur des cas (lors de la suppression du dernier élément ).
Conclusion: la suppression d’élément LinkedList est plus rapide que ArrayList.
Raison: LinkedList & # 8217; chaque élément conserve deux pointeurs (adresses) qui pointent vers les deux éléments voisins de la liste. Par conséquent, la suppression nécessite uniquement de modifier l'emplacement du pointeur dans les deux nœuds voisins (éléments) du nœud à supprimer. Dans ArrayList, tous les éléments doivent être décalés pour remplir l’espace créé par l’élément supprimé.
3) Arraylist (O(1)) LinkedList (O(n)) La méthode add donne <=> des performances alors que <=> donne <=> dans le pire des cas. La raison est la même que celle expliquée pour supprimer.
4) <=> <=> gère les index et les données d'élément tandis que <=> conserve les données d'élément et deux pointeurs pour les nœuds voisins
par conséquent, la consommation de mémoire dans LinkedList est comparativement élevée.
Il existe peu de similitudes entre ces classes:
- ArrayList et LinkedList sont tous deux des implémentations de l'interface List.
- Ils maintiennent tous les deux l'ordre d'insertion des éléments, ce qui signifie que, lors de l'affichage des éléments ArrayList et LinkedList, le jeu de résultats aurait le même ordre d'insertion dans la liste.
- Ces deux classes ne sont pas synchronisées et peuvent être synchronisées explicitement à l'aide de la méthode Collections.synchronizedList.
- Les <=> et <=> renvoyés par ces classes sont <=> (si la liste est structurellement modifiée à tout moment après la création de l'itérateur, de quelque manière que ce soit, sauf par le biais des <=> propres méthodes de suppression ou d'ajout, l'itérateur sera <=> a <=>).
Quand utiliser LinkedList et quand utiliser ArrayList?
- Comme expliqué ci-dessus, les opérations d'insertion et de suppression offrent de bonnes performances <=> dans <=> par rapport à <=>.
Par conséquent, s’il est nécessaire d’ajouter ou de supprimer fréquemment des applications, LinkedList est le meilleur choix.
- Les opérations de recherche (<=>) sont rapides dans <=> mais pas dans <=>
so S'il y a moins d'opérations d'ajout et de suppression et plus d'exigences en matière d'opérations de recherche, ArrayList serait votre meilleur choix.
L'opération get (i) dans ArrayList est plus rapide que LinkedList, car:
ArrayList : implémentation de tableau redimensionnable de l'interface de liste
LinkedList: Implémentation de la liste à double liaison des interfaces List et Deque
Les opérations qui indexent dans la liste parcourent la liste depuis le début ou la fin, selon ce qui est le plus proche de l'index spécifié.
1) Structure de données sous-jacente
La première différence entre ArrayList et LinkedList réside dans le fait qu’ArrayList est pris en charge par Array, tandis que LinkedList est pris en charge par LinkedList. Cela entraînera de nouvelles différences de performances.
2) LinkedList implémente Deque
Une autre différence entre ArrayList et LinkedList réside dans le fait qu’hormis l’interface List, LinkedList implémente également l’interface Deque, qui fournit les opérations premier entré, premier sorti pour add () et poll () ainsi que plusieurs autres fonctions Deque. 3) Ajouter des éléments dans ArrayList Ajouter un élément dans ArrayList est une opération O (1) si elle ne déclenche pas la redimensionnement de Array, auquel cas il devient O (log (n)). Par contre, ajouter un élément dans LinkedList est une opération O (1), car elle ne nécessite aucune navigation.
4) Suppression d'un élément d'une position
Afin de supprimer un élément d'un index particulier, par ex. en appelant remove (index), ArrayList effectue une opération de copie qui le rapproche de O (n), tandis que LinkedList doit passer à ce point, ce qui le rend également O (n / 2), car il peut traverser dans les deux sens en fonction de la proximité. .
5) Itérer sur ArrayList ou LinkedList
L'itération est l'opération O (n) pour LinkedList et ArrayList, où n est le numéro d'un élément.
6) Récupération d'un élément à partir d'une position
L'opération get (index) est O (1) dans ArrayList alors que son O (n / 2) dans LinkedList, car elle doit être parcourue jusqu'à cette entrée. Cependant, dans la notation Big O, O (n / 2) n’est que O (n) car nous ignorons les constantes.
7) Mémoire
LinkedList utilise un objet wrapper, Entry, qui est une classe imbriquée statique pour le stockage de données et deux nœuds next et previous, tandis que ArrayList stocke uniquement des données dans Array.
Ainsi, dans le cas d'ArrayList, les besoins en mémoire semblent inférieurs à ceux de LinkedList, sauf dans le cas où Array effectue l'opération de redimensionnement lorsqu'il copie le contenu d'un tableau à un autre.
Si Array est suffisamment grand, cela peut prendre beaucoup de mémoire et déclencher un Garbage Collection, ce qui peut ralentir le temps de réponse.
Parmi toutes les différences entre ArrayList et LinkedList, ArrayList semble être le meilleur choix que LinkedList dans presque tous les cas, sauf lorsque vous effectuez une opération add () fréquente plutôt que remove () ou get ().
Il est plus facile de modifier une liste liée que ArrayList, en particulier si vous ajoutez ou supprimez des éléments au début ou à la fin, car la liste liée conserve en interne les références de ces positions et qu'elles sont accessibles en temps O (1).
En d'autres termes, vous n'avez pas besoin de parcourir la liste liée pour atteindre la position où vous souhaitez ajouter des éléments. Dans ce cas, l'addition devient une opération O (n). Par exemple, insérer ou supprimer un élément au milieu d’une liste liée.
À mon avis, utilisez ArrayList sur LinkedList pour la plupart des applications pratiques en Java.
Les méthodes remove () et insert () ont toutes deux une efficacité d'exécution de O (n) pour ArrayLists et LinkedLists. Cependant, la raison du temps de traitement linéaire provient de deux raisons très différentes:
Dans une ArrayList, vous accédez à l'élément dans O (1), mais supprimer ou insérer quelque chose en fait un élément O (n) car tous les éléments suivants doivent être modifiés.
Dans une LinkedList, il faut O (n) pour atteindre l'élément souhaité, car nous devons commencer au tout début jusqu'à atteindre l'index souhaité. En fait, supprimer ou insérer est constant, car il suffit de changer 1 référence pour remove () et 2 références pour insert ().
Lequel des deux est plus rapide pour l'insertion et la suppression dépend de l'endroit où cela se produit. Si nous sommes plus près du début, la LinkedList sera plus rapide, car nous devons passer en revue relativement peu d'éléments. Si nous sommes proches de la fin, un ArrayList sera plus rapide, car nous y arriverons en un temps constant et nous n’aurons plus qu’à changer les quelques éléments restants qui le suivent. Lorsque cela est fait précisément au milieu, la LinkedList sera plus rapide, car parcourir n éléments est plus rapide que déplacer n valeurs.
Bonus: Bien qu'il n'y ait aucun moyen de rendre ces deux méthodes O (1) pour un ArrayList, il existe en fait un moyen de le faire dans LinkedLists. Disons que nous voulons parcourir toute la liste en supprimant et en insérant des éléments sur notre chemin. Habituellement, vous commenciez au tout début pour chaque élément à l’aide de LinkedList, nous pourrions aussi & "Save &"; l'élément actuel sur lequel nous travaillons avec un itérateur. Avec l'aide de l'Iterator, nous obtenons une efficacité de O (1) pour remove () et insert () lorsque nous travaillons dans une LinkedList. Je suis conscient du fait que c’est toujours le meilleur avantage en termes de performances d’une LinkedList par rapport à une ArrayList.
ArrayList étend AbstractList et implémente l'interface de liste. ArrayList est un tableau dynamique.
On peut dire qu'il a été créé pour surmonter les inconvénients des tableaux
La classe LinkedList étend AbstractSequentialList et implémente les interfaces List, Deque et Queue.
Performance
arraylist.get() est O (1) alors que linkedlist.get() est O (n)
arraylist.add() est O (1) et linkedlist.add() est 0 (1)
arraylist.contains() est O (n) et linkedlist.contains() est O (n)
arraylist.next() est O (1) et linkedlist.next() est O (1)
arraylist.remove() est O (n) alors que linkedlist.remove() est O (1)
En liste de lecteurs iterator.remove() est O (n)
alors que dans la liste chaînée <<> est O (1)
L'un des tests que j'ai vu ici n'effectue le test qu'une seule fois.Mais ce que j'ai remarqué, c'est que vous devez exécuter ces tests plusieurs fois et que leurs horaires finiront par converger.Fondamentalement, la JVM doit s'échauffer.Pour mon cas d'utilisation particulier, j'avais besoin d'ajouter/supprimer des éléments à un dernier qui s'élève à environ 500 éléments.Dans mes tests LinkedList est sorti plus vite, avec lié LinkedList arrivant dans environ 50 000 NS et ArrayList arrivant à environ 90 000 NS...donner ou prendre.Voir le code ci-dessous.
public static void main(String[] args) {
List<Long> times = new ArrayList<>();
for (int i = 0; i < 100; i++) {
times.add(doIt());
}
System.out.println("avg = " + (times.stream().mapToLong(x -> x).average()));
}
static long doIt() {
long start = System.nanoTime();
List<Object> list = new LinkedList<>();
//uncomment line below to test with ArrayList
//list = new ArrayList<>();
for (int i = 0; i < 500; i++) {
list.add(i);
}
Iterator it = list.iterator();
while (it.hasNext()) {
it.next();
it.remove();
}
long end = System.nanoTime();
long diff = end - start;
//uncomment to see the JVM warmup and get faster for the first few iterations
//System.out.println(diff)
return diff;
}
