Por qué ArrayDeque es mejor que LinkedList

Question

Estoy tratando de comprender por qué el ArrayDeque de Java es mejor que el 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 usándolo. No pude entender claramente la implementación de JDK en cuanto a la forma en que maneja las referencias de cabeza y cola.

Answer 1

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

Si necesita agregar/eliminar 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.

Answer 2

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

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

Answer 3

aunque ArrayDeque<E> y LinkedList<E> tienen tanto implementarse Deque<E> Interface, pero el ArrayDeque utiliza básicamente objeto de matriz E[] para mantener los elementos dentro de su objeto, por lo que generalmente utiliza el índice para la localización de los elementos de cabeza y de cola .

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

Answer 4

Creo que el cuello de botella de rendimiento principal en LinkedList es el hecho de que cada vez que se presiona hacia un extremo del deque, detrás de la escena la implementación asigna un nuevo nodo de lista vinculada, que esencialmente implica JVM/OS, y eso es caro. Además, cada vez que aparece desde cualquier lado, los nodos internos de LinkedList son elegibles para la recolección de basura y eso es más trabajo detrás de la escena.

Si puede ser de interés, tengo una prueba de que al agregar un elemento a ArrayList o ArrayDeque se ejecuta en tiempo constante amorido; consulte this.

Answer 5

Acceso a un elemento en ArrayDeque siempre más rápido se compara con LinkedList con O (1) para acceder a elementos. En la lista Vinculada, tomará O (N) para encontrar el último elemento.

ArrayDeque es eficiente de la memoria ya que no tiene que llevar un registro de nodo siguiente a diferencia de lista enlazada.

Incluso de acuerdo con la documentación de Java, se ha citado que

ArrayDeque es la implementación de tamaño variable de matriz de la interfaz deque.Deques de matriz no tienen restricciones de capacidad; crecen según sea necesario para apoyar el uso. No son seguros para subprocesos; en ausencia de sincronización externa, no admiten el acceso simultáneo por múltiples hilos. Los elementos nulos están prohibidos. Es probable que esta clase sea más rápida que Stack cuando se usa como una pila, y más rápida que LinkedList cuando se utiliza como una cola.

Benchmarking de estos dos demuestra que ArrayDeque es más rápido.

Answer 6

La complejidad del 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 ella a través de varios subprocesos y para que sean más rápidos.

Answer 7

Todas las personas que critican un LinkedList, pensar en cualquier otro tipo que ha estado utilizando List en Java, probablemente utiliza ArrayList y un LinkedList la mayor parte de las veces, ya que han sido antes de Java 6 y porque esos son los que se enseñan como una comenzar en la mayoría de los libros.

Pero eso no quiere decir que tomaría ciegamente el lado de LinkedList o ArrayDeque. Si desea saber, eche un vistazo al siguiente punto de referencia done by Brian.

La configuración de la 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.
• Mide el tiempo en términos de milisegundos.

Prueba Resultado:

• por debajo de 10.000 elementos, tanto LinkedList y pruebas ArrayDeque promedió en un nivel ms sub 1.
• A medida que aumentan los conjuntos de datos, las diferencias entre ArrayDeque y LinkedList se hacen más grandes.
• En el tamaño de prueba de 9,900,000 elementos, el enfoque LinkedList tomó ~ 165% más que el enfoque ArrayDeque.

Gráfico:

Para llevar:

• Si su requerimiento es el almacenamiento de 100 o 200 elementos, sería no hacer mucha diferencia usando cualquiera de las colas
• Sin embargo, si está desarrollando en el móvil, es posible que desee utilizar un ArrayListArrayDeque o con una buena suposición de la capacidad máxima que la lista puede ser requerido para ser debido a la estricta limitación de memoria.
• Una gran cantidad de código existe, escrita usando un LinkedList así ir con cuidado al decidir utilizar un ArrayDeque sobre todo porque no implementa la interfazList (creo que es lo suficientemente grande como razón). Puede ser que su base de código se comunique con la interfaz de la Lista de manera exhaustiva, lo más probable es que decida intervenir con ArrayDeque. Usarlo para implementaciones internas podría ser una buena idea ...