1.ArrayList implementa uma estrutura de dados baseada em matrizes dinâmicas e LinkedList implementa uma estrutura de dados baseada em listas vinculadas.
2. Para obter e definir acesso aleatório, ArrayList é melhor que LinkedList porque ArrayList pode ser posicionado aleatoriamente, enquanto LinkedList precisa mover o ponteiro para o nó passo a passo. (Pense com referência a matrizes e listas vinculadas)
3. Para as operações de adição e remoção de nova e exclusão, LinedList é mais vantajoso. Ele só precisa modificar o ponteiro, enquanto ArrayList precisa mover dados para preencher o espaço do objeto excluído.
ArrayList e LinkedList são duas classes de coleção usadas para armazenar uma série de referências de objetos. Por exemplo, podemos usar ArrayList para armazenar uma série de String ou Integer. Então, qual é a diferença de desempenho entre ArrayList e LinkedList? Quando você deve usar ArrayList e quando deve usar LinkedList?
um. complexidade de tempo
O primeiro ponto chave é que a implementação interna de ArrayList é baseada em um array de objetos básico. Portanto, quando ele usa o método get para acessar qualquer elemento da lista (acesso aleatório), é mais rápido que LinkedList. O método get no LinkedList verifica de uma extremidade à outra da lista em ordem. Para o LinkedList, não existe uma maneira mais rápida de acessar um elemento específico da lista.
Suponha que temos uma lista grande e os elementos nela foram classificados. Esta lista pode ser do tipo ArrayList ou do tipo LinkedList. Agora realizamos uma pesquisa binária nesta lista. veja o seguinte programa:
Tempo consumido do LinkedList: 2596
Este resultado não é fixo, mas basicamente o tempo do ArrayList é significativamente menor que o do LinkedList. Portanto LinkedList não deve ser usado neste caso. O método de pesquisa binária usa uma estratégia de acesso aleatório (randomaccess) e o LinkedList não suporta acesso aleatório rápido. O tempo consumido pelo acesso aleatório a uma LinkedList é proporcional ao tamanho da lista. Da mesma forma, o tempo consumido para acesso aleatório em ArrayList é fixo.
Isso significa que o ArrayList sempre tem um desempenho melhor que o LinkedList? Isso não é necessariamente verdade, em alguns casos o LinkedList tem desempenho melhor que o ArrayList e alguns algoritmos são mais eficientes quando implementados no LinkedList. Por exemplo, o desempenho é melhor ao usar o método Collections.reverse para reverter uma lista.
Veja um exemplo, se tivermos uma lista e quisermos realizar um grande número de operações de inserção e exclusão nela, neste caso LinkedList é uma escolha melhor. Considere o seguinte exemplo extremo, onde inserimos repetidamente um elemento no início de uma lista:
Neste momento, minha saída é: ArrayList leva: 2463
LinkedList leva: 15
Isso é completamente oposto ao resultado do exemplo anterior. Quando um elemento é adicionado ao início do ArrayList, todos os elementos existentes serão movidos para trás, o que significa sobrecarga de movimentação e cópia de dados. Por outro lado, adicionar um elemento ao início de uma LinkedList simplesmente atribui um registro ao elemento e depois ajusta os dois links. O custo de adicionar um elemento ao início de um LinkedList é fixo, enquanto o custo de adicionar um elemento ao início de um ArrayList é proporcional ao tamanho do ArrayList.
dois. complexidade do espaço
Existe uma classe interna privada no LinkedList, definida da seguinte forma:
entrada de classe estática privada {
Elemento objeto;
Entrada a seguir;
Entrada anterior;
}
Cada objeto Entry faz referência a um elemento na lista, bem como ao seu elemento anterior e ao próximo elemento na LinkedList. Um objeto LinkedList com 1.000 elementos terá 1.000 objetos Entry vinculados entre si, cada objeto correspondendo a um elemento da lista. Nesse caso, haverá muito overhead de espaço em uma estrutura LinkedList, pois ela precisa armazenar as informações relevantes desses 1000 objetos Entity.
ArrayList usa um array integrado para armazenar elementos. A capacidade inicial deste array é 10. Quando o array precisa crescer, a nova capacidade é obtida de acordo com a seguinte fórmula: nova capacidade = (capacidade antiga*3)/2+. 1, isto é, a capacidade aumentará cerca de 50% a cada vez. Isso significa que se você tiver um objeto ArrayList com um grande número de elementos, acabará com muito espaço desperdiçado. Esse desperdício é causado pela forma como o ArrayList funciona. Caso não haja espaço suficiente para armazenar o novo elemento, o array terá que ser realocado para que o novo elemento possa ser adicionado. A realocação do array causará uma queda drástica no desempenho. Se soubermos quantos elementos um ArrayList terá, podemos especificar a capacidade através do construtor. Também podemos usar o método trimToSize para remover o espaço desperdiçado após a alocação de ArrayList.
três. Resumir
ArrayList e LinkedList têm suas próprias vantagens e desvantagens em termos de desempenho e cada um tem seu próprio aplicativo. De modo geral, pode ser descrito da seguinte forma:
Resumo de desempenho:
| - | operação adicionar() | operação excluir() | operação de inserção | operação de valor de índice | operação de valor do iterador |
|---|---|---|---|---|---|
| ArrayList/Vetor/Pilha | bom | Diferença | Diferença | Excelente | Excelente |
| Lista vinculada | bom | bom | bom | Diferença | Excelente |
1. Tanto para ArrayList quanto para LinkedList, o custo de adicionar um elemento ao final da lista é fixo. Para ArrayList, ele adiciona principalmente um item ao array interno, apontando para o elemento adicionado, o que pode ocasionalmente fazer com que o array seja realocado para LinkedList, essa sobrecarga é uniforme, alocando um objeto Entry interno;
2. Inserir ou excluir um elemento no meio de um ArrayList significa que os elementos restantes da lista serão movidos enquanto inserir ou excluir um elemento no meio de um LinkedList tem um custo fixo;
3. LinkedList não suporta acesso eficiente a elementos aleatórios.
4. O desperdício de espaço do ArrayList se reflete principalmente na reserva de uma certa quantidade de espaço no final da lista, enquanto o consumo de espaço do LinkedList se reflete no fato de que cada elemento dele precisa consumir uma quantidade considerável de espaço.
Pode ser dito assim: Quando a operação é adicionar dados após uma coluna de dados em vez de na frente ou no meio, e você precisa acessar os elementos aleatoriamente, usar ArrayList proporcionará melhor desempenho quando sua operação estiver na frente de; uma coluna de dados Ao adicionar ou excluir dados no meio e acessar os elementos em ordem, você deve usar LinkedList.
A diferença entre ArrayList e Lista em java
Coleção de lista
A lista herda da interface da coleção. Lista é uma coleção ordenada. Os elementos da Lista podem ser obtidos/excluídos/inseridos com base no índice (número de sequência: a informação de posição do elemento na coleção).
Ao contrário da coleção Set, List permite elementos duplicados. Para elementos de objeto e1 e e2 que atendem às condições de e1.equals(e2), eles podem existir na coleção List ao mesmo tempo. Claro, também existem classes de implementação de List que não permitem elementos duplicados.
Ao mesmo tempo, List também fornece um método listIterator(), que retorna um objeto de interface ListIterator. Comparado com a interface Iterator, ListIterator adiciona métodos para adicionar, excluir e definir elementos, e também pode avançar ou retroceder.
A relação entre Lista e Coleção:
java.util.Collection[I]
+--java.util.List[I]
+--java.util.ArrayList [C]
+--java.util.LinkedList [C]
+--java.util.Vetor [C]
+--java.util.Stack [C]
As classes de implementação da interface List incluem principalmente ArrayList, LinkedList, Vector, Stack, etc.
Relacionamento pai-filho.
List é uma interface e ArrayList herda essa interface e a implementa.
Ao usá-lo, geralmente uso ArrayList. Nunca usei List. Você pode usá-lo assim: List list = new ArrayList();
Interface de coleção
Coleção é a interface de coleção mais básica. Uma Coleção representa um conjunto de Objetos, ou seja, os elementos da Coleção. Algumas Coleções permitem elementos idênticos e outras não. Alguns tipos e outros não. O Java SDK não fornece classes que herdam diretamente da Collection. As classes fornecidas pelo Java SDK são todas "subinterfaces" que herdam da Collection, como List e Set.
Todas as classes que implementam a interface Collection devem fornecer dois construtores padrão: um construtor sem parâmetros para criar uma Coleção vazia e um construtor de parâmetro Collection para criar uma nova Coleção. A Coleção de entrada possui os mesmos elementos. O último construtor permite ao usuário copiar uma coleção.
Como iterar cada elemento da coleção? Independentemente do tipo real de Coleção, ele suporta um método iterator(), que retorna um iterador que pode ser usado para acessar cada elemento da Coleção, um por um. O uso típico é o seguinte:
Iterator it = Collection.iterator(); // Obtenha um iterador
enquanto(it.hasNext()) {
Object obj = it.next(); // Obtém o próximo elemento
}
As duas interfaces derivadas da interface Collection são List e Set.
Interface de lista:
Lista é uma coleção ordenada. Usando esta interface, você pode controlar com precisão a posição de inserção de cada elemento. Os usuários podem acessar os elementos da Lista usando o índice (a posição do elemento na Lista, semelhante a um subscrito de array), que é semelhante a um array Java.
Ao contrário do Set mencionado abaixo, List permite os mesmos elementos.
Além do método iterator() necessário para a interface Collection, List também fornece um método listIterator(), que retorna uma interface ListIterator Comparado com a interface Iterator padrão, ListIterator possui mais alguns métodos add() e outros métodos, permitindo adições. Exclua, defina elementos e avance ou retroceda.
As classes comuns que implementam a interface List são LinkedList, ArrayList, Vector e Stack.
Classe LinkedList
LinkedList implementa a interface List e permite elementos nulos. Além disso, o LinkedList fornece métodos adicionais de obtenção, remoção e inserção no início ou no final do LinkedList. Essas operações permitem que LinkedList seja usado como pilha, fila ou deque.
Observe que LinkedList não possui métodos sincronizados. Se vários threads acessarem uma lista ao mesmo tempo, eles próprios deverão implementar a sincronização de acesso. Uma solução alternativa é construir uma lista sincronizada ao criar a lista:
Lista lista = Collections.synchronizedList(new LinkedList(...));
Classe ArrayList
ArrayList implementa arrays de tamanho variável. Permite todos os elementos, incluindo nulo. ArrayList não está sincronizado.
O tempo de execução dos métodos size, isEmpty, get e set é constante. No entanto, o custo do método add é uma constante amortizada e a adição de n elementos requer O(n) tempo. Outros métodos têm tempo de execução linear.
Cada instância de ArrayList possui uma capacidade (Capacity), que é o tamanho do array usado para armazenar elementos. Esta capacidade aumenta automaticamente à medida que novos elementos são adicionados, mas o algoritmo de crescimento não está definido. Quando um grande número de elementos precisa ser inserido, o método secureCapacity pode ser chamado para aumentar a capacidade do ArrayList antes da inserção para melhorar a eficiência da inserção.
Assim como LinkedList, ArrayList também não é sincronizado.
Resumo: Se operações como pilhas e filas estiverem envolvidas, você deve considerar o uso de List. Se precisar inserir e excluir elementos rapidamente, você deve usar LinkedList. Se precisar de acesso aleatório rápido aos elementos, você deve usar ArrayList.
Tente retornar a interface em vez do tipo real, como retornar List em vez de ArrayList, para que, se você precisar substituir ArrayList por LinkedList no futuro, o código do cliente não precise ser alterado. Isso é programação para abstração.