ArrayList em imagens

Oi! A lição de hoje sobre ArrayListserá mais fácil e mais difícil do que as lições anteriores. Será mais difícil porque hoje vamos olhar sob o capô ArrayListe estudar o que acontece durante várias operações. Por outro lado, esta lição quase não terá código. São principalmente fotos e explicações. Bem, vamos lá :) Como você já sabe, ArrayListtem um array comum dentro, que funciona como um armazenamento de dados. Na maioria dos casos, não especificamos o tamanho exato da lista. Mas o array interno deve ter algum tamanho! E assim acontece. Seu tamanho padrão é 10 .

public static void main(String[] args) {
   ArrayList<Car> cars = new ArrayList<>();
}

Primeiro, vamos ver como é a adição de novos elementos. A primeira ordem do dia é verificar se o array interno tem espaço suficiente no array interno e se cabe mais um elemento. Se houver espaço, o novo elemento será adicionado ao final da lista. Quando dizemos "até o fim", não queremos dizer a última posição no array (isso seria estranho). Queremos dizer a posição após o último elemento atual. Seu índice será cars.size(). Nossa lista está vazia no momento ( cars.size() == 0). Assim, o novo elemento será adicionado na posição 0.

ArrayList<Car> cars = new ArrayList<>();
Car ferrari = new Car("Ferrari 360 Spider");
cars.add(ferrari);

Isso é claro o suficiente. O que acontece se inserirmos no meio, ou seja, entre outros elementos?

public static void main(String[] args) {
   ArrayList<Car> cars = new ArrayList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");
   Car ford = new Car("Ford Modneo");
  
   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
  
   cars.add(1, ford);// add ford to cell 1, which is already occupied
}

Novamente, primeiro verificamos se há espaço suficiente no array. Se houver espaço suficiente, então os elementos são deslocados para a direita , começando pela posição onde inserimos o novo elemento. Estamos inserindo na posição 1. Em outras palavras, o elemento da posição 3 é copiado para a posição 4, o elemento 2 para a posição 3 e o elemento 1 para a posição 2. Então nosso novo elemento é inserido em seu lugar. O elemento anterior (bugatti) já foi copiado de lá para uma nova posição. Agora vamos ver como esse processo acontece se não houver locais para inserir novos elementos no array. Naturalmente, há primeiro uma verificação para ver se há espaço suficiente. Se não houver espaço suficiente, um novo array é criado dentro doArrayListcujo tamanho é o tamanho do array antigo vezes 1,5 mais 1. No nosso caso, o tamanho do novo array será 16. Todos os elementos atuais serão copiados para lá imediatamente. A matriz antiga será excluída pelo coletor de lixo e somente a nova matriz expandida permanecerá. Agora há espaço para um novo elemento. Estamos inserindo na posição 3, que está ocupada. Agora o procedimento familiar começa. Todos os elementos, começando com o índice 3, são deslocados uma posição para a direita e o novo elemento é adicionado discretamente. E a inserção está feita! E terminamos com a inserção. Agora vamos falar sobre a remoção de itens . Você deve se lembrar de que encontramos um problema ao trabalhar com arrays: a remoção de elementos cria "buracos" em um array.a cada remoção, e tivemos que escrever nosso próprio código a cada vez para realizar essa mudança. ArrayList segue o mesmo princípio, mas já implementa esse mecanismo. É assim que fica: E no final obtemos o que queremos: O lamboelemento foi removido. Aqui removemos um elemento do meio. Claramente, remover um elemento do final da lista é mais rápido, pois o elemento é simplesmente removido sem a necessidade de deslocar todos os outros. Vamos falar novamente por um momento sobre as dimensões do array interno e como ele está organizado na memória. Expandir uma matriz requer alguns recursos. Assim, não crie umArrayListcom o tamanho padrão se tiver certeza de que terá pelo menos 100 elementos. A matriz interna teria que ser expandida 6 vezes no momento em que você inserisse o 100º elemento, e todos os elementos teriam que ser deslocados a cada vez.

• de 10 elementos a 16
• de 16 elementos para 25
• de 25 a 38
• de 38 a 58
• de 58 a 88
• de 88 a 133 (ou seja, tamanho do antigo array vezes 1,5 mais 1)

Como você pode imaginar, isso é bastante intensivo em recursos. Portanto, se você já conhece (mesmo que aproximadamente) o número de itens necessários, é melhor criar uma lista com um array de tamanho específico:

ArrayList<Car> cars = new ArrayList<>(100);

Agora a memória para um array de 100 elementos será alocada de uma só vez, tornando o array mais eficiente (não precisará ser expandido). Essa estratégia também tem um outro lado. Quando você remove objetos de um ArrayList, o tamanho do array interno não diminui automaticamente. Suponha que temos um ArrayListcom uma matriz interna completamente cheia de 88 elementos: Conforme o programa é executado, removemos 77 elementos, então apenas 11 permanecem: Você já adivinhou qual é o problema? Você entendeu, uso ineficiente de memória! Estamos usando apenas 11 posições aqui, mas alocamos memória para 88 elementos. Isso é 8 vezes mais do que precisamos! Nesse caso, podemos otimizar nosso uso de memória com um dos ArrayListmétodos especiais da classe:trimToSize(). Este método "corta" o comprimento do array interno para o número de elementos atualmente armazenados nele. Agora alocamos apenas a quantidade de memória necessária! :)