Por que ArrayDeque é melhor que LinkedList

Estou tentando entender por que o ArrayDeque do Java é melhor que o LinkedList do Java, pois ambos implementam a interface Deque.

Quase não vejo alguém usando ArrayDeque em seu código. Se alguém esclarecer como o ArrayDeque é implementado, seria útil.

Se eu entender, ficarei mais confiante em usá-lo. Eu não conseguia entender claramente a implementação do JDK quanto à maneira como ele gerencia as referências de cabeçalho e cauda.

Estruturas vinculadas são possivelmente a pior estrutura para iterar com uma falta de cache em cada elemento. Além disso, eles consomem muito mais memória.

Se você precisar adicionar / remover ambas as extremidades, o ArrayDeque é significativamente melhor que uma lista vinculada. O acesso aleatório a cada elemento também é O (1) para uma fila cíclica.

A única operação melhor de uma lista vinculada é remover o elemento atual durante a iteração.

Acredito que o principal gargalo de desempenho LinkedListé o fato de que, sempre que você avança para qualquer extremidade do deque, nos bastidores, a implementação aloca um novo nó de lista vinculado, que envolve essencialmente JVM / OS, e isso é caro. Além disso, sempre que você salta de qualquer extremidade, os nós internos LinkedListse tornam elegíveis para a coleta de lixo e isso é mais trabalhoso nos bastidores. Além disso, como os nós da lista vinculada são alocados aqui e ali, o uso do cache da CPU não trará muitos benefícios.

Se puder ser interessante, tenho uma prova de que adicionar (anexar) um elemento ArrayListou ser ArrayDequeexecutado em tempo constante amortizado; consulte isso .

ArrayDeque é novo no Java 6, e é por isso que muitos códigos (especialmente projetos que tentam ser compatíveis com versões anteriores do Java) não o usam.

É "melhor" em alguns casos, porque você não está alocando um nó para cada item a ser inserido; todos os elementos são armazenados em uma matriz gigante, que é redimensionada se ficar cheia.

Todas as pessoas que criticam a LinkedList, pensam em todos os outros usuários que usam ListJava, provavelmente usam ArrayListe na LinkedListmaioria das vezes porque estiveram antes do Java 6 e porque essas são as que estão sendo ensinadas como um começo na maioria dos livros.

Mas, isso não significa, eu cegamente tomar LinkedList's ou ArrayDeques lado'. Se você quiser saber, dê uma olhada no benchmark abaixo feito por Brian .

A configuração do teste considera:

• Cada objeto de teste é uma cadeia de 500 caracteres. Cada String é um objeto diferente na memória.
• O tamanho da matriz de teste será variado durante os testes.
• Para cada combinação de tamanho de matriz / implementação de fila, 100 testes são executados e o tempo médio por teste é calculado.
• Cada teste consiste em preencher cada fila com todos os objetos e removê-los todos.
• Meça o tempo em termos de milissegundos.

Resultado do teste:

• Abaixo de 10.000 elementos, os testes LinkedList e ArrayDeque tiveram uma média de um nível inferior a 1 ms.
• À medida que os conjuntos de dados aumentam, as diferenças entre o tempo médio de teste ArrayDeque e LinkedList aumentam.
• No tamanho do teste de 9.900.000 elementos, a abordagem LinkedList demorou ~ 165% a mais que a abordagem ArrayDeque.

Gráfico:

Leve embora:

• Se o seu requisito estiver armazenando 100 ou 200 elementos, não faria muita diferença usar qualquer uma das filas.
• No entanto, se você estiver desenvolvendo em dispositivos móveis, convém usar um ArrayListou ArrayDequecom um bom palpite sobre a capacidade máxima que a lista pode exigir devido a uma restrição restrita de memória.
• Existe um monte de código, escrito usando um LinkedListprocedimento tão cuidadoso ao decidir usar um, ArrayDequeespecialmente porque ele não implementa a Listinterface (acho que esse é o motivo). Pode ser que sua base de código converse com a interface da lista extensivamente, provavelmente e você decida usar um ArrayDeque. Usá-lo para implementações internas pode ser uma boa ideia ...

ArrayDeque e LinkedList estão implementando a interface Deque , mas a implementação é diferente.

Principais diferenças:

1. A classe ArrayDeque é a implementação redimensionável da interface Deque e a classe LinkedList é a implementação da lista

2. Elementos NULL podem ser adicionados ao LinkedList, mas não no ArrayDeque

3. ArrayDeque é mais eficiente que o LinkedList para adicionar e remover operações nas duas extremidades e a implementação do LinkedList é eficiente para remover o elemento atual durante a iteração

4. A implementação LinkedList consome mais memória que o ArrayDeque

Portanto, se você não precisa suportar elementos NULL e procurar menos memória e eficiência de adicionar / remover elementos nas duas extremidades, o ArrayDeque é o melhor

Consulte a documentação para mais detalhes.

embora ArrayDeque<E>e LinkedList<E>tenham ambos implementado a Deque<E>interface, mas o ArrayDeque usa basicamente o array de objetos E[]para manter os elementos dentro do objeto, portanto geralmente usa o índice para localizar os elementos de cabeçalho e cauda.

Em uma palavra, funciona apenas como Deque (com todo o método de Deque), no entanto, usa a estrutura de dados da matriz. Quanto a qual é o melhor, depende de como e onde você os usa.

Nem sempre é esse o caso.

Por exemplo, no caso abaixo linkedlist, o desempenho é melhor que o ArrayDequedo 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;
    }
}

A complexidade de tempo para ArrayDeque para acessar um elemento é O (1) e para LinkList é O (N) para acessar o último elemento. O ArrayDeque não é seguro para threads, sendo necessária a sincronização manual para que você possa acessá-lo através de vários threads e para que sejam mais rápidos.