¿Por qué es ArrayDeque mejor que LinkedList?

Estoy tratando de entender por qué ArrayDeque de Java es mejor que LinkedList de Java, ya que ambos implementan la interfaz Deque.

Apenas veo a alguien usando ArrayDeque en su código. Si alguien arroja más luz sobre cómo se implementa ArrayDeque, sería útil.

Si lo entiendo, estaré más seguro de usarlo. No podía entender claramente la implementación de JDK en cuanto a la forma en que maneja las referencias de cabeza y cola.

Las estructuras vinculadas son posiblemente la peor estructura para iterar con una falta de caché en cada elemento. Además, consumen mucha más memoria.

Si necesita agregar / quitar ambos extremos, ArrayDeque es significativamente mejor que una lista vinculada. El acceso aleatorio de cada elemento también es O (1) para una cola cíclica.

La única mejor operación de una lista vinculada es eliminar el elemento actual durante la iteración.

Creo que el principal cuello de botella en el rendimiento LinkedListes el hecho de que cada vez que avanza hacia cualquier extremo de la deque, detrás de escena, la implementación asigna un nuevo nodo de lista vinculada, que esencialmente involucra JVM / OS, y eso es costoso. Además, cada vez que aparece desde cualquier extremo, los nodos internos se LinkedListvuelven elegibles para la recolección de basura y eso es más trabajo detrás de escena. Además, dado que los nodos de la lista vinculada se asignan aquí y allá, el uso de la memoria caché de la CPU no proporcionará muchos beneficios.

Si puede ser de interés, tengo una prueba de que agregar (agregar) un elemento ArrayListo ArrayDequeejecuta en tiempo constante amortizado; refiérase a esto .

ArrayDeque es nuevo con Java 6, por lo que una gran cantidad de código (especialmente proyectos que intentan ser compatibles con versiones anteriores de Java) no lo usan.

Es "mejor" en algunos casos porque no está asignando un nodo para cada elemento para insertar; en cambio, todos los elementos se almacenan en una matriz gigante, que se redimensiona si se llena.

Es probable que todas las personas que critican a LinkedList, piensen en todos los demás tipos que han estado usando Listen Java, ArrayListy la LinkedListmayoría de las veces porque han estado antes de Java 6 y porque esos son los que se enseñan como comienzo en la mayoría de los libros.

Sin embargo, eso no quiere decir, me gustaría tener a ciegas LinkedList's o ArrayDeque' lado s. Si quieres saber, echa un vistazo al siguiente punto de referencia realizado por Brian .

La configuración de prueba considera:

• Cada objeto de prueba es una cadena de 500 caracteres. Cada cadena es un objeto diferente en la memoria.
• El tamaño de la matriz de prueba variará durante las pruebas.
• Para cada combinación de tamaño de matriz / implementación de cola, se ejecutan 100 pruebas y se calcula el tiempo promedio por prueba.
• Cada prueba consiste en llenar cada cola con todos los objetos y luego eliminarlos todos.
• Mida el tiempo en términos de milisegundos.

Resultado de la prueba:

• Por debajo de 10,000 elementos, las pruebas LinkedList y ArrayDeque promediaron en un nivel inferior a 1 ms.
• A medida que los conjuntos de datos se hacen más grandes, las diferencias entre el tiempo de prueba promedio ArrayDeque y LinkedList se hacen más grandes.
• Con un tamaño de prueba de 9,900,000 elementos, el enfoque LinkedList tomó ~ 165% más tiempo que el enfoque ArrayDeque.

Grafico:

Para llevar:

• Si su requerimiento es almacenar 100 o 200 elementos, no haría mucha diferencia usando cualquiera de las Colas.
• Sin embargo, si está desarrollando en un dispositivo móvil, es posible que desee utilizar una ArrayListo ArrayDequecon una buena estimación de la capacidad máxima que puede requerir la lista debido a la estricta restricción de memoria.
• Existe una gran cantidad de código, escrito usando una LinkedListbanda de rodadura con mucho cuidado al decidir usar un, ArrayDequeespecialmente porque NO implementa la Listinterfaz (creo que esa es una razón lo suficientemente grande). Es posible que su base de código se comunique ampliamente con la interfaz de la Lista, lo más probable es que decida saltar con un ArrayDeque. Usarlo para implementaciones internas podría ser una buena idea ...

ArrayDeque y LinkedList están implementando la interfaz Deque , pero la implementación es diferente.

Diferencias clave

1. La clase ArrayDeque es la implementación de matriz redimensionable de la interfaz Deque y la clase LinkedList es la implementación de la lista

2. Se pueden agregar elementos NULL a LinkedList pero no en ArrayDeque

3. ArrayDeque es más eficiente que LinkedList para agregar y quitar operaciones en ambos extremos y la implementación de LinkedList es eficiente para eliminar el elemento actual durante la iteración

4. La implementación de LinkedList consume más memoria que ArrayDeque

Entonces, si no tiene que admitir elementos NULL && buscando menos memoria && eficiencia de agregar / eliminar elementos en ambos extremos, ArrayDeque es el mejor

Consulte la documentación para más detalles.

aunque ArrayDeque<E>y LinkedList<E>ambos han implementado la Deque<E>interfaz, pero ArrayDeque usa básicamente una matriz de objetos E[]para mantener los elementos dentro de su objeto, por lo que generalmente usa el índice para ubicar los elementos de cabeza y cola.

En una palabra, simplemente funciona como Deque (con todos los métodos de Deque), pero usa la estructura de datos de la matriz. En cuanto a cuál es mejor, depende de cómo y dónde los use.

Ese no es siempre el caso.

Por ejemplo, en el caso a continuación linkedlisttiene un mejor rendimiento que de ArrayDequeacuerdo con 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;
        // 👇 here ,linkedlist works better
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        boolean left2right=true;
        while(!queue.isEmpty())
        {
            int size=queue.size();
            LinkedList<Integer> t=new LinkedList<>();
            while(size-->0)
            {
                TreeNode tree=queue.remove();
                if(left2right)  
                    t.add(tree.val);
                else
                    t.addFirst(tree.val);
                if(tree.left!=null)
                {
                    queue.add(tree.left);
                }
                if(tree.right!=null)
                {
                    queue.add(tree.right);
                }
            }
            rs.add(t);
            left2right=!left2right;
        }
        return rs;
    }
}

La complejidad de tiempo para ArrayDeque para acceder a un elemento es O (1) y para LinkList es O (N) para acceder al último elemento. ArrayDeque no es seguro para subprocesos, por lo que la sincronización manual es necesaria para que pueda acceder a través de múltiples subprocesos y que sean más rápidos.