Pourquoi ArrayDeque est-il meilleur que LinkedList ?

Question

J'essaie de comprendre pourquoi le ArrayDeque de Java est meilleur que le LinkedList de Java car ils implémentent tous deux l'interface Deque.

Je vois rarement quelqu'un utiliser ArrayDeque dans son code. Si quelqu'un m'éclaire sur la façon dont ArrayDeque est implémenté, ce serait utile.

Si je le comprends, je serai plus confiant en l'utilisant. Je n'ai pas pu comprendre clairement l'implémentation du JDK quant à la manière dont il gère les références tête et queue.

Answer 1

Les structures liées sont probablement la pire structure à itérer avec un manque de cache sur chaque élément. En plus de cela, elles consomment beaucoup plus de mémoire.

Si vous avez besoin d'ajouter/supprimer les deux extrémités, ArrayDeque est nettement meilleur qu'une liste chaînée. L'accès aléatoire à chaque élément est également O(1) pour une file cyclique.

La seule meilleure opération d'une liste chaînée est la suppression de l'élément courant pendant l'itération.

Answer 2

Je pense que le principal goulot d'étranglement en matière de performances dans le domaine des LinkedList est le fait qu'à chaque fois que vous poussez vers une extrémité de la deque, l'implémentation alloue en arrière-plan un nouveau nœud de liste liée, ce qui implique essentiellement la JVM/OS, et c'est coûteux. De plus, à chaque fois que l'on "pop" à partir d'une extrémité, les noeuds internes de la liste liée de LinkedList deviennent éligibles pour la collecte des déchets et cela représente plus de travail derrière la scène. De plus, comme les nœuds de la liste chaînée sont alloués ici et là, l'utilisation du cache du CPU n'apportera pas beaucoup d'avantages.

Si cela peut vous intéresser, j'ai prouvé que l'ajout (l'ajout) d'un élément à la liste des éléments de la liste des éléments de la liste des éléments de la liste des éléments. ArrayList o ArrayDeque s'exécute en temps constant amorti ; voir este .

Answer 3

ArrayDeque est une nouveauté de Java 6, ce qui explique pourquoi de nombreux codes (notamment les projets qui tentent d'être compatibles avec des versions antérieures de Java) ne l'utilisent pas.

C'est "mieux" dans certains cas parce que vous n'allouez pas un nœud pour chaque élément à insérer ; au lieu de cela, tous les éléments sont stockés dans un tableau géant, qui est redimensionné s'il est plein.

Answer 4

ArrayDeque y LinkedList mettent en œuvre Deque mais la mise en œuvre est différente.

Principales différences :

1. Le site ArrayDeque est l'implémentation du tableau redimensionnable de la classe Deque et l'interface LinkedList est l'implémentation de la liste

2. Des éléments NULL peuvent être ajoutés à LinkedList mais pas dans ArrayDeque

3. ArrayDeque est plus efficace que le LinkedList pour l'opération d'ajout et de suppression aux deux extrémités et la mise en œuvre de LinkedList est efficace pour supprimer l'élément courant pendant l'itération.

4. Le site LinkedList consomme plus de mémoire que l'implémentation ArrayDeque

Donc, si vous ne devez pas prendre en charge les éléments NULL && vous cherchez à réduire la mémoire && l'efficacité de l'ajout/suppression d'éléments aux deux extrémités, ArrayDeque est le meilleur

Se référer à documentation pour plus de détails.

Answer 5

Bien que ArrayDeque<E> y LinkedList<E> ont tous deux mis en œuvre Deque<E> mais ArrayDeque utilise fondamentalement un tableau d'objets. E[] pour conserver les éléments à l'intérieur de son objet, il utilise donc généralement l'index pour localiser les éléments de tête et de queue.

En un mot, il fonctionne comme Deque (avec toutes les méthodes de Deque), mais utilise la structure de données des tableaux. Pour ce qui est de savoir lequel est le meilleur, cela dépend de comment et où vous les utilisez.