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

Je ne pense pas que ArrayDeque est meilleur que LinkedList . Ils sont différents.

ArrayDeque est plus rapide que LinkedList en moyenne. Mais pour ajouter un élément, ArrayDeque prend un temps constant amorti, et LinkedList prend un temps constant.

Pour les applications sensibles au facteur temps qui exigent que toutes les opérations prennent un temps constant, il faut seulement LinkedList doit être utilisé.

ArrayDeque L'implémentation de l'UE utilise des tableaux et nécessite un redimensionnement. Occasionnellement, lorsque le tableau est plein et qu'il faut ajouter un élément, le redimensionnement prend un temps linéaire, ce qui entraîne l'utilisation de l'option add() méthode qui prend un temps linéaire. Cela pourrait être un désastre si l'application est très sensible au temps.

Une explication plus détaillée de l'implémentation de ces deux structures de données par Java est disponible dans le document " Algorithmes, première partie "cours sur Coursera proposé par l'Université de Princeton, enseigné par Wayne et Sedgewick. Le cours est gratuit pour le public.

Les détails sont expliqués dans la vidéo "Redimensionnement des tableaux" dans la section "Piles et files d'attente" de la "Semaine 2".

Answer 2

Pas toujours le cas.

Par exemple, dans le cas ci-dessous linkedlist a de meilleures performances que ArrayDeque selon le leetcode 103.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> rs=new ArrayList<>();
        if(root==null)
            return rs;
        //

Answer 3

La complexité du temps pour ArrayDeque pour accéder à un élément est O(1) et celle pour LinkList est O(N) pour accéder au dernier élément. ArrayDeque n'est pas thread safe, une synchronisation manuelle est donc nécessaire pour que vous puissiez y accéder à travers plusieurs threads et qu'ils soient plus rapides.