Quando usar LinkedList sobre ArrayList em Java?

StackOverflow https://stackoverflow.com/questions/322715

Pergunta

Eu sempre fui um para usar simplesmente: 

List<String> names = new ArrayList<>();

Eu uso a interface como o nome do tipo de portabilidade , de modo que quando eu faço perguntas como estas que eu posso refazer meu código.

Quando deve LinkedList ser usado sobre ArrayList e vice-versa?

Foi útil?

Solução

Resumo ArrayList com ArrayDeque são preferíveis em muitos mais casos de uso que LinkedList. Se você não tiver certeza -. Começar com ArrayList

LinkedList e ArrayList são duas implementações diferentes da interface List. implementos LinkedList-lo com uma lista duplamente vinculada. ArrayList implementa-lo com uma matriz dinamicamente re-dimensionamento.

Tal como acontece com operações de lista e matriz ligados padrão, os vários métodos têm diferentes tempos de execução algorítmicos.

Para LinkedList<E>

  • get(int index) O (n) (com N / 4 passos em média)
  • add(E element) é O (1)
  • add(int index, E element) O (n) (com n / 4 passos, em média), mas O (1) quando index = 0 <--- principal benefício do LinkedList<E>
  • remove(int index) O (n) (com N / 4 passos em média)
  • Iterator.remove() é O (1) . <--- principal benefício do LinkedList<E>
  • ListIterator.add(E element) é O (1) Este é um dos principais benefícios da LinkedList<E>

Nota: Muitas das operações precisa n / 4 passos em média, constante número de passos no melhor dos casos (por exemplo index = 0), e n / 2 passos no pior dos casos (no meio da lista)

Para ArrayList<E>

  • get(int index) é O (1) <--- principal benefício do ArrayList<E>
  • add(E element) O (1) amortizados, mas O (n) pior caso uma vez que a matriz deve ser redimensionada e copiado
  • add(int index, E element) O (n) (com N / 2 passos em média)
  • remove(int index) O (n) (com N / 2 passos em média)
  • Iterator.remove() O (n) (com N / 2 passos em média)
  • ListIterator.add(E element) O (n) (com N / 2 passos em média)

Nota: Muitas das operações precisa n / 2 etapas, em média, constante número de passos na melhor das hipóteses (Fim da lista), n passos no pior caso (início da lista)

LinkedList<E> permite inserções em tempo constante ou remoções usando iteradores , mas apenas acesso sequencial de elementos. Em outras palavras, você pode andar a lista para a frente ou para trás, mas encontrar uma posição na lista leva tempo proporcional ao tamanho da lista. Javadoc diz "operações que índice para a lista irá percorrer a lista desde o início ou o fim, o que for mais perto" , para que esses métodos são O (n) ( n / 4 passos) em média, embora O (1) para index = 0.

ArrayList<E>, por outro lado, permitem rápido acesso de leitura aleatória, assim você pode pegar qualquer elemento em tempo constante. Mas a adição ou remoção de qualquer lugar, mas o fim requer mudando todos os últimos elementos mais, seja para fazer uma abertura ou preencher a lacuna. Além disso, se você adicionar mais elementos do que a capacidade da matriz subjacente, uma nova matriz (1,5 vezes o tamanho) é alocado, e a matriz de idade é copiado para o novo, assim que adicionar a um ArrayList é O (n ) , no pior caso, mas constante, em média.

Assim, dependendo das operações que você pretende fazer, você deve escolher as implementações em conformidade. Iteração sobre qualquer tipo de lista é praticamente igualmente barato. (Iteração sobre um ArrayList é tecnicamente mais rápido, mas a menos que você está fazendo algo realmente sensíveis ao desempenho, você não deve se preocupar com isso -. Ambos são constantes)

Os principais benefícios do uso de um LinkedList surgem quando você re-uso iterato existenters e para inserir elementos de remover. Estas operações podem, então, ser feito em O (1) , alterando a lista apenas localmente. Em uma lista de matriz, o restante das necessidades de matriz para ser foi movida (ou seja copiado). Por outro lado, buscando em um meio LinkedList seguintes as ligações em O (n) ( N / 2 passos) para o pior caso, ao passo que numa ArrayList a lata posição pretendida ser calculado matematicamente e acessados ??em O (1) .

Outra vantagem de usar um LinkedList surgem quando você adicionar ou remover da cabeça da lista, uma vez que essas operações são O (1) , enquanto eles são O (n) para ArrayList. Note-se que ArrayDeque pode ser uma boa alternativa para LinkedList para adicionar e remover a partir da cabeça, mas não é um List.

Além disso, se você tem grandes listas, tenha em mente que o uso de memória também é diferente. Cada elemento de um LinkedList tem mais sobrecarga desde apontadores para os elementos seguintes e anteriores são também armazenados. ArrayLists não tem essa sobrecarga. No entanto, ArrayLists levar até o máximo de memória é alocada para a capacidade, independentemente de elementos realmente foram adicionados.

A capacidade inicial padrão de um ArrayList é muito pequena (10 de Java 1,4-1,8). Mas desde a implementação subjacente é uma matriz, a matriz deve ser redimensionada se você adicionar uma grande quantidade de elementos. Para evitar o alto custo de redimensionamento quando você sabe que está indo para adicionar um monte de elementos, construir o ArrayList com maior capacidade inicial.

Outras dicas

Até agora, ninguém parece ter abordado o consumo de memória de cada uma dessas listas, além do consenso geral de que a LinkedList é "muito mais" do que um ArrayList então eu fiz alguns números para demonstrar exatamente o quanto ambas as listas ocupam para N referências nulas.

Uma vez que as referências são ou 32 ou 64 bits (mesmo quando null) em seus sistemas relativos, eu incluí 4 conjuntos de dados de 32 e 64 LinkedLists pouco e ArrayLists.

Nota: Os tamanhos mostrados para as linhas ArrayList são para listas aparadas - Na prática, a capacidade da matriz de suporte em um ArrayList é geralmente maior do que o seu elemento atual contar.

Nota 2: (graças BeeOnRope) Como CompressedOops é padrão agora a partir de meados JDK6 e para cima, os valores abaixo para máquinas de 64 bits será basicamente coincidir com o seu 32-bit homólogos, a menos que você especificamente desligá-lo.

Gráfico do LinkedList e ArrayList Nº de elementos x Bytes

O resultado mostra claramente que LinkedList é muito mais do que ArrayList, especialmente com uma contagem muito elevada elemento. Se a memória é um fator, orientar clara de LinkedLists.

As fórmulas I utilizados acompanhamento, deixe-me saber se eu tiver errado qualquer coisa e eu vou consertá-la. 'B' é 4 ou 8 a 32 ou 64 sistemas de bits, e 'n' é o número de elementos. Note-se a razão para os mods é porque todos os objetos em java vai ocupar um múltiplo de 8 bytes espaço independentemente de tudo é usado ou não.

ArrayList:

ArrayList object header + size integer + modCount integer + array reference + (array oject header + b * n) + MOD(array oject, 8) + MOD(ArrayList object, 8) == 8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8) + MOD(8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8), 8)

LinkedList:

LinkedList object header + size integer + modCount integer + reference to header + reference to footer + (node object overhead + reference to previous element + reference to next element + reference to element) * n) + MOD(node object, 8) * n + MOD(LinkedList object, 8) == 8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n + MOD(8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n, 8)

ArrayList é o que você quer. LinkedList é quase sempre um (performance) bug.

Por LinkedList suga:

  • Ele usa lotes de objetos de memória pequeno e, portanto, impactos de desempenho em todo o processo.
  • Lotes de pequenos objetos são ruins para cache-localidade.
  • Qualquer operação indexada requer um percurso, isto é, tem O desempenho (n). Esta não é óbvio no código fonte, levando a algoritmos O (n) mais lento do que se foi usado ArrayList.
  • Começar bom desempenho é complicado.
  • Mesmo quando o desempenho big-O é o mesmo que ArrayList, ele é provavelmente vai ser significativamente mais lento de qualquer maneira.
  • É chocante ver LinkedList na fonte, porque é provavelmente a escolha errada.

Como alguém que tem vindo a fazer engenharia desempenho operacional em serviços SOA Web muito grande escala para cerca de uma década, eu preferiria o comportamento de LinkedList sobre ArrayList. Enquanto a taxa de transferência de estado estacionário de LinkedList é pior e, portanto, pode levar a comprar mais hardware - o comportamento de ArrayList sob pressão pode levar a aplicações em um cluster expandindo suas matrizes em sincronicidade próximo e para grandes tamanhos de matriz poderia levar à falta de capacidade de resposta no aplicativo e uma interrupção, quando sob pressão, o que é um comportamento catastrófico.

Da mesma forma, você pode obter melhor rendimento em um aplicativo a partir do padrão de transferência coletor de lixo titular, mas quando você começa aplicativos java com 10GB amontoa você pode acabar travando o aplicativo por 25 segundos durante uma GCs completa que faz com que o tempo limite e falhas em SOA aplicativos e sopra seus SLAs se ocorrer com muita freqüência. Mesmo que o coletor de CMS tem mais recursos e não conseguir o mesmo rendimento brutos, é a melhor escolha muito porque tem latência mais previsível e menor.

ArrayList é apenas uma escolha melhor para o desempenho se tudo que você quer dizer com o desempenho é o rendimento e você pode ignorar a latência. Na minha experiência no meu trabalho eu não posso ignorar a latência do pior caso. 

Algorithm           ArrayList   LinkedList
seek front            O(1)         O(1)
seek back             O(1)         O(1)
seek to index         O(1)         O(N)
insert at front       O(N)         O(1)
insert at back        O(1)         O(1)
insert after an item  O(N)         O(1)

Algoritmos: Big-Oh Notation

ArrayLists são bons para escrever uma vez-ler-muitos ou appenders, mas ruim em adicionar / remover a partir da frente ou no meio.

Sim, eu sei, esta é uma questão antiga, mas eu vou atirar em meus dois centavos:

LinkedList é quase sempre a escolha errada, em termos de performance. Há alguns algoritmos muito específicos onde um LinkedList é chamado para, mas esses são muito, muito raro e o algoritmo irá normalmente especificamente depender da capacidade da LinkedList para inserir e elementos de exclusão no meio da lista de forma relativamente rápida, uma vez que você navegou lá com um ListIterator.

Não é um caso de uso comum no qual LinkedList Supera ArrayList: o de uma fila. No entanto, se o seu objetivo é o desempenho, em vez de LinkedList você também deve considerar o uso de um ArrayBlockingQueue (se você pode determinar um limite superior sobre o seu tamanho da fila antes do tempo, e pode dar ao luxo de alocar toda a memória na frente), ou este CircularArrayList implementação . (Sim, é a partir de 2001, de forma que você precisa generify-lo, mas eu tenho rácios de desempenho comparável ao que está citado no artigo agora em uma JVM recente)

É uma questão de eficiência. LinkedList é rápido para adicionar e excluir elementos, mas lento para acessar um elemento específico. ArrayList é rápido para acessar um elemento específico, mas pode ser lento para adicionar a cada extremidade, e especialmente lento para apagar no meio.

matriz vs ArrayList vs LinkedList vs Vector vai mais em profundidade, como faz Linked Lista .

Correta ou Incorreta: Por favor executar teste localmente e decidir por si mesmo

Editar / Remover é mais rápido em LinkedList que ArrayList.

ArrayList, apoiado por Array, que deve ser o dobro do tamanho, é pior em grande aplicação volume.

A seguir é o resultado de teste de unidade para cada operation.Timing é dada em nanossegundos. 

Operation                       ArrayList                      LinkedList  

AddAll   (Insert)               101,16719                      2623,29291 

Add      (Insert-Sequentially)  152,46840                      966,62216

Add      (insert-randomly)      36527                          29193

remove   (Delete)               20,56,9095                     20,45,4904

contains (Search)               186,15,704                     189,64,981

Aqui está o código: 

import org.junit.Assert;
import org.junit.Test;

import java.util.*;

public class ArrayListVsLinkedList {
    private static final int MAX = 500000;
    String[] strings = maxArray();

    ////////////// ADD ALL ////////////////////////////////////////
    @Test
    public void arrayListAddAll() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        watch.start();
        arrayList.addAll(stringList);
        watch.totalTime("Array List addAll() = ");//101,16719 Nanoseconds
    }

    @Test
    public void linkedListAddAll() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);

        watch.start();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(stringList);
        watch.totalTime("Linked List addAll() = ");  //2623,29291 Nanoseconds
    }

    //Note: ArrayList is 26 time faster here than LinkedList for addAll()

    ///////////////// INSERT /////////////////////////////////////////////
    @Test
    public void arrayListAdd() {
        Watch watch = new Watch();
        List<String> arrayList = new ArrayList<String>(MAX);

        watch.start();
        for (String string : strings)
            arrayList.add(string);
        watch.totalTime("Array List add() = ");//152,46840 Nanoseconds
    }

    @Test
    public void linkedListAdd() {
        Watch watch = new Watch();

        List<String> linkedList = new LinkedList<String>();
        watch.start();
        for (String string : strings)
            linkedList.add(string);
        watch.totalTime("Linked List add() = ");  //966,62216 Nanoseconds
    }

    //Note: ArrayList is 9 times faster than LinkedList for add sequentially

    /////////////////// INSERT IN BETWEEN ///////////////////////////////////////

    @Test
    public void arrayListInsertOne() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX + MAX / 10);
        arrayList.addAll(stringList);

        String insertString0 = getString(true, MAX / 2 + 10);
        String insertString1 = getString(true, MAX / 2 + 20);
        String insertString2 = getString(true, MAX / 2 + 30);
        String insertString3 = getString(true, MAX / 2 + 40);

        watch.start();

        arrayList.add(insertString0);
        arrayList.add(insertString1);
        arrayList.add(insertString2);
        arrayList.add(insertString3);

        watch.totalTime("Array List add() = ");//36527
    }

    @Test
    public void linkedListInsertOne() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(stringList);

        String insertString0 = getString(true, MAX / 2 + 10);
        String insertString1 = getString(true, MAX / 2 + 20);
        String insertString2 = getString(true, MAX / 2 + 30);
        String insertString3 = getString(true, MAX / 2 + 40);

        watch.start();

        linkedList.add(insertString0);
        linkedList.add(insertString1);
        linkedList.add(insertString2);
        linkedList.add(insertString3);

        watch.totalTime("Linked List add = ");//29193
    }


    //Note: LinkedList is 3000 nanosecond faster than ArrayList for insert randomly.

    ////////////////// DELETE //////////////////////////////////////////////////////
    @Test
    public void arrayListRemove() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        arrayList.addAll(stringList);
        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        arrayList.remove(searchString0);
        arrayList.remove(searchString1);
        watch.totalTime("Array List remove() = ");//20,56,9095 Nanoseconds
    }

    @Test
    public void linkedListRemove() throws Exception {
        Watch watch = new Watch();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(Arrays.asList(strings));

        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        linkedList.remove(searchString0);
        linkedList.remove(searchString1);
        watch.totalTime("Linked List remove = ");//20,45,4904 Nanoseconds
    }

    //Note: LinkedList is 10 millisecond faster than ArrayList while removing item.

    ///////////////////// SEARCH ///////////////////////////////////////////
    @Test
    public void arrayListSearch() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        arrayList.addAll(stringList);
        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        arrayList.contains(searchString0);
        arrayList.contains(searchString1);
        watch.totalTime("Array List addAll() time = ");//186,15,704
    }

    @Test
    public void linkedListSearch() throws Exception {
        Watch watch = new Watch();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(Arrays.asList(strings));

        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        linkedList.contains(searchString0);
        linkedList.contains(searchString1);
        watch.totalTime("Linked List addAll() time = ");//189,64,981
    }

    //Note: Linked List is 500 Milliseconds faster than ArrayList

    class Watch {
        private long startTime;
        private long endTime;

        public void start() {
            startTime = System.nanoTime();
        }

        private void stop() {
            endTime = System.nanoTime();
        }

        public void totalTime(String s) {
            stop();
            System.out.println(s + (endTime - startTime));
        }
    }


    private String[] maxArray() {
        String[] strings = new String[MAX];
        Boolean result = Boolean.TRUE;
        for (int i = 0; i < MAX; i++) {
            strings[i] = getString(result, i);
            result = !result;
        }
        return strings;
    }

    private String getString(Boolean result, int i) {
        return String.valueOf(result) + i + String.valueOf(!result);
    }
}

ArrayList é essencialmente uma matriz. LinkedList é implementado como uma lista encadeada dupla.

O get é bastante clara. O (1) para ArrayList, porque ArrayList permitir o acesso aleatório por meio do índice. O (n) para LinkedList, porque ele precisa encontrar o índice primeiro. Nota: existem diferentes versões do add e remove.

LinkedList é mais rápido em adicionar e remover, mas mais lento no get. Em breve, LinkedList deve ser preferido se:

  1. não há grande número de acesso aleatório do elemento
  2. há um grande número de operações de adicionar / remover

=== ArrayList ===

  • add (E e)
    • adicione no final do ArrayList
    • requerem custo redimensionamento memória.
    • O (n) pior, O (1) amortizado
  • add (int index, E elemento)
    • Adicionar a uma posição de índice específica
    • exigem mudança e possível memória redimensionamento custo
    • O (n)
  • remove (int index)
    • remover um elemento especificado
    • exigem mudança e possível memória redimensionamento custo
    • O (n)
  • remove (Object o)
    • remover a primeira ocorrência do elemento especificado a partir dessa lista
    • necessidade de procurar o elemento primeiro, e depois deslocando & possível memória redimensionamento custo
    • O (n)

=== LinkedList ===

  • add (E e)

    • adicionar ao final da lista
    • O (1)

  • add (int index, E elemento)

    • inserção na posição especificada
    • necessidade de encontrar a primeira posição
    • O (n)
  • remove ()
    • remover primeiro elemento da lista
    • O (1)
  • remove (int index)
    • elemento remove com índice especificado
    • necessidade de encontrar o primeiro elemento
    • O (n)
  • remove (Object o)
    • remover a primeira ocorrência do elemento especificado
    • necessidade de encontrar o primeiro elemento
    • O (n)

Aqui está uma figura de programcreek.com (add e remove são do primeiro tipo, isto é, adicionar um elemento para o fim da lista e remover o elemento na posição especificada na lista.):

enter descrição da imagem aqui

Joshua Bloch, autor de LinkedList:

Alguém realmente usar LinkedList? Eu escrevi isso, e eu nunca usá-lo.

Link: https://twitter.com/joshbloch/status/583813919019573248

Eu sinto muito pela resposta por ser não tão informativo como as outras respostas, mas eu pensei que seria o mais interessante e auto-explicativo.

ArrayList é aleatoriamente acessíveis, enquanto LinkedList é realmente barato para expandir e remover elementos de. Para a maioria dos casos, ArrayList é bom.

A menos que você tenha criado grandes listas e mediu um gargalo, você provavelmente nunca precisa se preocupar com a diferença.

Se o seu código tem add(0) e remove(0), use uma LinkedList e é mais bonita métodos addFirst() e removeFirst(). Caso contrário, o uso ArrayList.

E, claro, Goiaba 's ImmutableList é seu melhor amigo.

Eu sei que este é um post antigo, mas eu honestamente não posso acreditar que ninguém mencionou que implementos LinkedList Deque. Basta olhar para os métodos em Deque (e Queue); se você quiser uma comparação justa, tente executar LinkedList contra ArrayDeque e fazer uma comparação de recursos-de-recurso.

Aqui é a notação Big-O, tanto ArrayList e LinkedList e também CopyOnWrite-ArrayList:

ArrayList 

get                 O(1)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

LinkedList 

get                 O(n)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(1)
iterator.remove     O(1)

CopyOnWrite-ArrayList 

get                 O(1)
add                 O(n)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

Com base nestes você tem que decidir o que escolher. :)

TL; DR. devido à arquitetura do computador moderno, ArrayList será significativamente mais eficiente para quase qualquer caso de uso possível - e, portanto, LinkedList deve ser evitado, exceto alguns casos muito originais e extremas

Em teoria, ListaLigada tem uma junta (1) para o add(E element)

Também adicionando um elemento no meio de uma lista deve ser muito eficiente.

A prática é muito diferente, como LinkedList é um Hostile Cache estrutura de dados. De desempenho POV - há muito pouco casos em que LinkedList poderia ser melhor desempenho do que o Cache-friendly ArrayList

.

Aqui estão os resultados de um benchmark testar elementos inserção em locais aleatórios. Como você pode ver - a lista de matriz se muito mais eficiente, embora, em teoria, cada inserção no meio da lista exigirá "mover" o n elementos posteriores da série (valores mais baixos são melhores):

enter descrição da imagem aqui

Trabalho em um hardware geração posterior (maior, caches mais eficientes) - os resultados são ainda mais conclusivo:

enter descrição da imagem aqui

LinkedList leva muito mais tempo para realizar o mesmo trabalho. fonte Código Fonte

Há duas razões principais para isso:

  1. principalmente - que os nós do LinkedList estão espalhados aleatoriamente em toda a memória. RAM ( "Random Access Memory") não é realmente aleatória e blocos de necessidade de memória precisa ser recuperado para cache. Esta operação leva tempo, e quando tais buscas acontecem com freqüência - as páginas de memória na necessidade de cache para ser substituído o tempo todo -> erros de cache -> Cache não é eficiente. elementos ArrayList são armazenados na memória contínua -. que é exatamente o que a arquitetura CPU moderno está otimizando para

  2. Secundária LinkedList necessário para segurar / ponteiros para a frente, o que significa 3 vezes o consumo de memória por valor armazenado em relação a ArrayList.

DynamicIntArray , aliás, é um Int ArrayList personalizado implementação de retenção (tipo primitivo) e não objetos - daí todos os dados são realmente armazenados adjacente -., portanto, ainda mais eficiente

A chave elementos para se lembrar é que o custo de buscar bloco de memória, é mais significativo do que o custo acessando uma única célula de memória. É por isso que leitor de 1MB de memória seqüencial é de até X400 vezes mais rápido do que ler esta quantidade de dados de diferentes blocos de memória: 

Latency Comparison Numbers (~2012)
----------------------------------
L1 cache reference                           0.5 ns
Branch mispredict                            5   ns
L2 cache reference                           7   ns                      14x L1 cache
Mutex lock/unlock                           25   ns
Main memory reference                      100   ns                      20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy             3,000   ns        3 us
Send 1K bytes over 1 Gbps network       10,000   ns       10 us
Read 4K randomly from SSD*             150,000   ns      150 us          ~1GB/sec SSD
Read 1 MB sequentially from memory     250,000   ns      250 us
Round trip within same datacenter      500,000   ns      500 us
Read 1 MB sequentially from SSD*     1,000,000   ns    1,000 us    1 ms  ~1GB/sec SSD, 4X memory
Disk seek                           10,000,000   ns   10,000 us   10 ms  20x datacenter roundtrip
Read 1 MB sequentially from disk    20,000,000   ns   20,000 us   20 ms  80x memory, 20X SSD
Send packet CA->Netherlands->CA    150,000,000   ns  150,000 us  150 ms

Fonte: Latência Números cada programador deve saber

Apenas para fazer o ponto ainda mais claro, por favor, verifique o valor de referência de adição de elementos para o início da lista. Este é um caso de uso em que, em teoria, a LinkedList deve realmente brilhar, e ArrayList deve apresentar resultados pobres ou mesmo pior caso:

enter descrição da imagem aqui

Nota: este é um ponto de referência da lib C ++ Std, mas a minha experiência anterior mostrou o C ++ e Java resultados são muito semelhantes. Source Code

Copiar uma massa seqüencial de memória é um operção otimizados pelas CPUs modernas - mudando teoria e realmente fazendo, mais uma vez, ArrayList / Vector muito mais eficiente

Créditos: Todos os benchmarks postadas aqui são criados por Kjell Hedström . Mesmo mais dados podem ser encontrados no seu blog

Vamos comparar LinkedList e ArrayList w.r.t. abaixo parâmetros:

1. Implementação

ArrayList é a implementação de array redimensionável da interface de lista, enquanto

LinkedList é a implementação lista duplamente vinculada da interface lista.

2. Desempenho

  • get (int index) ou operação de busca

    ArrayList get (int index) é executado de operação em tempo constante ou seja O (1), enquanto

    LinkedList get (int index) tempo de operação de execução é O (n).

    A razão por trás ArrayList ser mais rápido do que é ListaLigada que ArrayList utiliza um sistema baseado índice para os seus elementos, uma vez que utiliza internamente uma estrutura de dados de matriz, por outro lado,

    LinkedList não fornece acesso baseado em índice para seus elementos, uma vez que repete a partir do início ou no final (o que for mais próxima) para recuperar o nó no índice do elemento especificado.

  • insert () ou add (Object) operação

    As inserções em LinkedList são geralmente rápido como comparar a ArrayList. Em ListaLigada adição ou inserção é O (1) operação.

    Enquanto em ArrayList , se a matriz é a full ou seja pior dos casos, há um custo adicional de redimensionamento da matriz e copiar elementos para a nova matriz, o que torna tempo de execução de operação de adição em ArrayList O ( n), caso contrário, é O (1).

  • remove (int) operação

    Remover operação em ListaLigada é geralmente o mesmo que ArrayList isto é O (n).

    Em LinkedList , existem dois métodos remove sobrecarregados. um é remover () sem qualquer parâmetro que remove a cabeça da lista e é executado em tempo O constante (1). O outro método de remoção sobrecarregado em ListaLigada é remover (int) ou remover (objecto) que remove o objecto ou int transmitido como um parâmetro. Este método percorre a LinkedList até que encontrou o objeto e desvinculá-la da lista original. Assim, este método de execução é O (n).

    Enquanto em ArrayList método remove (int) envolve a cópia de elementos da idade matriz para nova matriz actualizada, daí o seu tempo de execução é O (n).

3. Reverter Iterator

ListaLigada pode ser repetido em sentido inverso utilizando descendingIterator () enquanto

não há descendingIterator () em ArrayList , por isso precisamos de escrever nosso próprio código para iterar sobre os ArrayList em sentido inverso.

4. Capacidade inicial

Se o construtor não está sobrecarregado, então ArrayList cria uma lista vazia de capacidade inicial de 10, enquanto

LinkedList única constrói a lista vazia sem qualquer capacidade inicial.

5. Memória Overhead

sobrecarga de memória no LinkedList é mais em comparação com ArrayList como um nó no LinkedList precisa manter os endereços do seguinte e anterior nó. Enquanto

Em ArrayList cada índice só mantém o objeto real (dados).

Fonte

Além dos outros argumentos bons acima, você deve observar interface de implementos ArrayList RandomAccess, enquanto implementos LinkedList Queue.

Então, de alguma forma eles abordar ligeiramente diferentes problemas, com diferença de eficiência e comportamento (ver a sua lista de métodos).

Uma lista de matriz é essencialmente um array com métodos para adicionar itens etc. (e você deve usar uma lista genérica em vez disso). É uma colecção de itens que podem ser acedidas através de um indexador (por exemplo, [0]). Implica uma progressão de um item para outro.

A vinculado lista especifica uma progressão de um item para a próxima (item A -> ponto b). Você pode obter o mesmo efeito com uma lista de matriz, mas uma lista ligada absolutamente diz o item é suposto a seguir o anterior.

Ela depende de quais operações você vai estar fazendo mais na lista.

ArrayList é mais rápido para acessar um valor indexado. É muito pior quando inserir ou excluir objetos.

Para saber mais, leia qualquer artigo que fala sobre a diferença entre matrizes e listas ligadas.

Eu costumo usar um sobre o outro com base nas complexidades de tempo das operações que eu executar em que lista particular. 

|---------------------|---------------------|--------------------|------------|
|      Operation      |     ArrayList       |     LinkedList     |   Winner   |
|---------------------|---------------------|--------------------|------------|
|     get(index)      |       O(1)          |         O(n)       | ArrayList  |
|                     |                     |  n/4 steps in avg  |            |
|---------------------|---------------------|--------------------|------------|
|      add(E)         |       O(1)          |         O(1)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     | O(n) in worst case  |                    |            |
|---------------------|---------------------|--------------------|------------|
|    add(index, E)    |       O(n)          |         O(n)       | LinkedList |
|                     |     n/2 steps       |      n/4 steps     |            |
|                     |---------------------|--------------------|            |
|                     |                     |  O(1) if index = 0 |            |
|---------------------|---------------------|--------------------|------------|
|  remove(index, E)   |       O(n)          |         O(n)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     |     n/2 steps       |      n/4 steps     |            |
|---------------------|---------------------|--------------------|------------|
|  Iterator.remove()  |       O(n)          |         O(1)       | LinkedList |
|  ListIterator.add() |                     |                    |            |
|---------------------|---------------------|--------------------|------------|


|--------------------------------------|-----------------------------------|
|              ArrayList               |            LinkedList             |
|--------------------------------------|-----------------------------------|
|     Allows fast read access          |   Retrieving element takes O(n)   |
|--------------------------------------|-----------------------------------|
|   Adding an element require shifting | o(1) [but traversing takes time]  |
|       all the later elements         |                                   |
|--------------------------------------|-----------------------------------|
|   To add more elements than capacity |
|    new array need to be allocated    |
|--------------------------------------|

Uma característica importante de uma lista ligada (o que eu não li em outra resposta) é a concatenação de duas listas. Com uma disposição deste é O (n) (+ sobrecarga de alguns reatribuições) com uma lista ligada este é apenas o (1) ou S (2); -)

Importante : Para Java seu LinkedList isso não é verdade! Consulte Existe um método concat rápido para lista ligada em Java?

Eu li as respostas, mas há um cenário onde eu sempre usar um LinkedList sobre um ArrayList que eu quero compartilhar de ouvir opiniões:

Toda vez que eu tinha um método que retorna uma lista de dados obtidos a partir de um DB Eu sempre uso um LinkedList.

Meu raciocínio era que, porque é impossível saber exatamente quantos resultados que estou recebendo, não haverá desperdício de memória (como no ArrayList com a diferença entre a capacidade eo número real de elementos), e não haveria tempo desperdiçado tentando duplicar a capacidade.

No que diz um ArrayList, concordo que, pelo menos, você deve sempre usar o construtor com a capacidade inicial, para minimizar a duplicação das matrizes, tanto quanto possível.

ArrayList e LinkedList têm seus próprios prós e contras.

ArrayList usa endereço de memória contígua comparação com LinkedList que usa ponteiros para o próximo nó. Então, quando você quiser procurar um elemento em um ArrayList é mais rápido do que fazê n iterações com LinkedList.

Por outro lado, inserção e exclusão em um LinkedList são muito mais fácil, porque você só tem que mudar os ponteiros enquanto um ArrayList implica a utilização de operação de deslocamento para qualquer inserção ou exclusão.

Se você tem operações de recuperação freqüentes em seu uso app um ArrayList. Se você tiver de inserção frequente e eliminação usar um LinkedList.

ArrayList e LinkedList ambos os implementos List interface e seus métodos e resultados são quase idênticos. No entanto, existem algumas diferenças entre eles que fazem um melhor sobre a outra, dependendo da exigência.

ArrayList Vs LinkedList

1) operação de busca Search: ArrayList é muito rápido em comparação com a operação de busca LinkedList. get(int index) em ArrayList dá o desempenho de O(1) enquanto o desempenho LinkedList é O(n).

Reason: ArrayList mantém sistema baseado índice para seus elementos, uma vez que usa a estrutura de dados de matriz implicitamente que o torna mais rápido para pesquisar um elemento na lista. Nos outros implementos LinkedList lado lista que requer a travessia através de todos os elementos para pesquisar um elemento duplamente ligada.

2) operação Deletion: LinkedList remover dá desempenho O(1) enquanto ArrayList dá um desempenho variável:. O(n) no pior caso (ao remover primeiro elemento) e O(1) no melhor dos casos (Ao remover último elemento)

Conclusão: Elemento LinkedList eliminação é mais rápida em comparação com ArrayList.

Motivo: LinkedList é cada elemento mantém dois ponteiros (endereços) que aponta para a ambos os elementos vizinhos na lista. Por isso, a remoção requer apenas a mudança na localização do ponteiro nos dois nós vizinhos (elementos) do nó que vai ser removido. Enquanto Em ArrayList todos os elementos precisam ser deslocado para preencher o espaço criado pelo elemento removido.

3) Método Inserts Performance: LinkedList add dá desempenho O(1) enquanto ArrayList dá O(n) no pior caso. A razão é mesmo como explicado para remover.

4) Memory Overhead: ArrayList mantém índices e os dados do elemento enquanto LinkedList mantém os dados de elemento e dois apontadores para nós vizinho

, consequentemente, o consumo de memória é alta em ListaLigada comparativamente.

Há poucas semelhanças entre essas classes que são as seguintes:

  • Ambos ArrayList e LinkedList são a implementação da interface List.
  • Ambos manter a ordem de inserção elementos que meios durante a exibição de ArrayList e LinkedList elementos do conjunto de resultados seria ter a mesma ordem em que os elementos foi inserido na lista.
  • Ambas estas classes não são sincronizados e podem ser feitas explicitamente sincronizado usando o método Collections.synchronizedList.
  • O iterator e listIterator retornado por essas classes são fail-fast (se a lista é estruturalmente modificada a qualquer momento após o iterador é criado, de forma alguma, exceto através do iterator’s própria remover ou adicionar métodos, o iterador irá throw um ConcurrentModificationException).

Quando usar LinkedList e quando usar ArrayList?

  • Como explicado acima das operações de inserir e remover dar boa (O(1)) desempenho em LinkedList comparação com ArrayList(O(n)).

    Portanto, se há uma exigência de adição freqüente e exclusão no aplicativo, em seguida, LinkedList é uma melhor escolha.

  • Pesquisa operações (get method) são rápidos em Arraylist (O(1)) mas não em LinkedList (O(n))

    Assim, se houver menos adicionar e remover operações e mais procurar exigência operações, ArrayList seria sua melhor aposta.

A operação get (i) em ArrayList é mais rápido que LinkedList, porque:
ArrayList: Resizable-array implementação da interface List
LinkedList: implementação lista duplamente vinculada das interfaces de lista e deque

As operações que índice para a lista irá percorrer a lista desde o início ou o fim, o que for mais perto do índice especificado.

1) subjacente na estrutura de dados

A primeira diferença entre ArrayList e LinkedList vem com o fato de que ArrayList é apoiado pela matriz, enquanto LinkedList é apoiado por LinkedList. Isto levará a mais diferenças no desempenho.

2) LinkedList implementa Deque

Outra diferença entre ArrayList e LinkedList é que, além da interface List, LinkedList também implementa interface de Deque, que fornece pela primeira vez em operações primeiro a sair para add () e poll () e várias outras funções deque. 3) Adição de elementos em ArrayList elemento Adicionando em ArrayList é O (1) operação, se isso não acontecer gatilho re-tamanho de matriz, no caso em que ele se torna O (log (n)), Por outro lado, acrescentando um elemento em LinkedList é O (1) operação, uma vez que não requer qualquer navegação.

4) A remoção de um elemento de uma posição

De modo a remover um elemento de um índice específico e.g. ligando para remover (índice), ArrayList executa uma operação de cópia que faz com que seja perto de O (n) enquanto ListaLigada necessita de atravessar a esse ponto, que também faz com que seja o (n / 2), uma vez que podem atravessar a partir de qualquer direcção com base na proximidade .

5) iteração sobre ArrayList ou LinkedList

Iteração é a operação de O (n) para ambos ListaLigada e ArrayList onde n é um número de um elemento.

6) Recuperar elemento a partir de uma posição

A operação de obtenção (índice) é O (1) em ArrayList enquanto a sua O (n / 2) em ListaLigada, uma vez que necessita para percorrer até que a entrada. Embora, em Big O notação O (n / 2) é apenas O (n) porque ignoramos constantes lá.

7) de memória

LinkedList usa um objeto de invólucro, de entrada, que é uma classe aninhada estática para armazenar dados e dois nós seguinte e anterior, enquanto ArrayList apenas armazena os dados em ordem.

Assim requisito de memória parece menos no caso de ArrayList que LinkedList exceto para o caso em que executa matriz a operação re-size quando ele copia o conteúdo de um array para outro.

Se Array é grande o suficiente que pode levar uma grande quantidade de memória em que a coleta de ponto e gatilho de lixo, o que pode retardar o tempo de resposta.

De todas as diferenças acima mencionadas entre ArrayList vs LinkedList, Parece ArrayList é a escolha melhor do que LinkedList em quase todos os casos, exceto quando você faz um add frequente () operação que remove () ou get ().

É mais fácil modificar uma lista ligada de ArrayList, especialmente se você está adicionando ou removendo elementos de início ou final, porque lista ligada mantém internamente referências dessas posições e eles são acessíveis em O (1) tempo.

Em outras palavras, você não precisa atravessar a lista ligada para alcançar a posição em que deseja adicionar elementos, nesse caso, além torna-se O funcionamento (n). Por exemplo, inserir ou excluir um elemento no meio de uma lista ligada.

Na minha opinião, o uso ArrayList sobre LinkedList para a maioria da finalidade prática em Java.

Ambos remover () e inserto () têm uma eficiência de tempo de execução de O (n) para ambos os ArrayLists e Linked. No entanto, a razão por trás o tempo de processamento linear vem de duas razões muito diferentes:

Em um ArrayList, você chegar ao elemento em O (1), mas na verdade remover ou inserir algo faz com que seja O (n) porque todos os seguintes elementos precisam ser alterados.

Em um LinkedList, leva O (n) para obter realmente para o elemento desejado, porque temos de começar no início até chegar ao índice desejado. Na verdade, a remoção ou a inserção é constante, porque apenas tem que mudar uma referência para remover () 2 e as referências para a inserção ().

Qual dos dois é mais rápido para inserir e remover depende de onde isso acontece. Se estamos mais perto do início do LinkedList será mais rápido, porque temos que passar por relativamente poucos elementos. Se estamos mais perto do fim de um ArrayList será mais rápido, porque nós chegar lá a tempo constante e só tem que mudar os poucos restantes elementos que o seguem. Quando feito precisamente no meio do LinkedList será mais rápido porque passando por n elementos é mais rápido do que se deslocam n valores.

Bonus: Enquanto não há nenhuma maneira de fazer estes dois métodos O (1) para um ArrayList, há realmente uma maneira de fazer isso no Linked. Vamos dizer que queremos passar por toda a lista de remoção e inserção de elementos em nosso caminho. Normalmente, você iria começar desde o início, para cada elemento usando o LinkedList, poderíamos também "salvar" o elemento atual que estamos trabalhando com um Iterator. Com a ajuda do Iterator, ficamos com uma eficiência O (1) para remove () e insert () quando se trabalha em um LinkedList. Tornando-o único benefício de desempenho Eu estou ciente de onde um LinkedList é sempre melhor do que um ArrayList.

ArrayList estende AbstractList e implementos a lista de interfaces. ArrayList é matriz dinâmica.
Pode-se dizer que ele foi basicamente criado para superar as desvantagens de matrizes
A classe LinkedList estende interface List, Deque, e Queue AbstractSequentialList e implementos.
desempenho
arraylist.get() é O (1), enquanto que linkedlist.get() é O (n)
arraylist.add() é O (1) e linkedlist.add() é 0 (1)
arraylist.contains() é O (n) andlinkedlist.contains() é O (n)
arraylist.next() é O (1) e linkedlist.next() é O (1)
arraylist.remove() é O (n) enquanto que linkedlist.remove() é O (1)
Em matrizes
iterator.remove() é O (n) enquanto que em
ListaLigada
iterator.remove()is O (1)

Um dos testes que eu vi aqui só conduz o teste uma vez. Mas o que eu tenho notado é que você precisa para executar esses testes muitas vezes e, eventualmente, seus tempos irá convergir. Basicamente, a JVM precisa para aquecer. Para o meu caso de uso particular que eu precisava para adicionar itens / Remover a um passado que cresce para cerca de 500 itens. Em meus testes LinkedList saiu mais rápido, com LinkedList ligada vindo em torno de 50.000 NS e ArrayList chegando a cerca de 90.000 NS ... mais ou menos. Veja o código abaixo. 

public static void main(String[] args) {
    List<Long> times = new ArrayList<>();
    for (int i = 0; i < 100; i++) {
        times.add(doIt());
    }
    System.out.println("avg = " + (times.stream().mapToLong(x -> x).average()));
}

static long doIt() {
    long start = System.nanoTime();
    List<Object> list = new LinkedList<>();
    //uncomment line below to test with ArrayList
    //list = new ArrayList<>();
    for (int i = 0; i < 500; i++) {
        list.add(i);
    }

    Iterator it = list.iterator();
    while (it.hasNext()) {
        it.next();
        it.remove();
    }
    long end = System.nanoTime();
    long diff = end - start;
    //uncomment to see the JVM warmup and get faster for the first few iterations
    //System.out.println(diff)
    return diff;
}
Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top