Java ArrayList em imagens

Olá! A palestra de hoje ArrayListserá, por um lado, mais simples e, por outro, mais difícil que as anteriores. É mais difícil, porque hoje vamos olhar “nos bastidores” ArrayListe estudar o que acontece durante as operações. Por outro lado, quase não haverá código nesta palestra - principalmente imagens e explicações. Então vamos lá :) Como você já sabe, dentro de ArrayList'a existe um array comum, 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! Isto é verdade. Seu tamanho padrão é [10] .

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

Primeiro, vamos ver como é adicionar um novo elemento. Em primeiro lugar, é feita uma verificação para ver se há espaço suficiente no array interno e se caberá mais um elemento. Se houver espaço, o novo elemento será adicionado ao final da lista. Quando dizemos “até o fim”, não nos referimos à última célula do array (isso seria estranho). Isso se refere à célula próxima ao último elemento atual. Seu índice será igual a cars.size(). Nossa lista está vazia no momento ( cars.size() = 0). Assim, um novo elemento será adicionado à célula com índice 0.

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

Tudo está claro aqui. O que acontecerá se a inserção for feita no meio, ou seja, entre vários 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);//добавляем ford в ячейку 1, которая уже занята
}

Novamente, ele primeiro verifica se há espaço suficiente no array. Se houver espaço suficiente, os elementos são deslocados para a direita a partir da célula onde inserimos o novo elemento. Colamos na célula com índice 1. Ou seja, o elemento da célula 3 é copiado para a célula 4, o elemento 2 para a célula 3, o elemento 1 para a célula 2. Depois disso, nosso novo elemento é colado no lugar. O elemento anterior ( bugatti) já foi copiado de lá para um novo local. Agora vamos descobrir como esse processo aconteceria se não houvesse espaço para inserção no array. Primeiro, é claro, é feita uma verificação para ver se há espaço suficiente. Se descobrir que não há espaço suficiente, ArrayListum novo array de tamanho (tamanho de OldArray * 1,5) + 1 é criado dentro de 'a. No nosso caso, o novo array terá um tamanho de 16 células. Todos os elementos atuais serão copiados para lá imediatamente. A matriz antiga será excluída pelo coletor de lixo e apenas a nova e expandida permanecerá. Agora há espaço livre para o novo elemento. Colamos na célula 3, que está ocupada. Agora começa o procedimento familiar. Todos os elementos começando no índice 3 são deslocados uma célula para a direita e um novo elemento é adicionado silenciosamente. E agora a inserção foi bem-sucedida! Nós resolvemos a inserção. Agora vamos falar sobre a remoção de elementos . Como você se lembra, ao trabalhar com arrays, encontramos um problema: quando os excluímos, restavam “buracos” neles. A única solução era deslocar os elementos para a esquerda cada vez que eles eram excluídos, e você mesmo tinha que escrever o código para a mudança. ArrayListfunciona com o mesmo princípio, mas nele esse mecanismo já está implementado automaticamente. É assim que parece: E no final obtemos o resultado desejado: O elemento lambofoi excluído com sucesso. Aqui fizemos uma remoção do meio. É claro que excluir do final da lista será mais rápido, pois o elemento desejado é removido sem deslocar todos os outros. Vamos dar uma olhada no tamanho do array interno e seu armazenamento na memória. A expansão do array é um processo que consome uma certa quantidade de recursos. Portanto, você não deve criar ArrayListcom o tamanho padrão se tiver certeza de que terá pelo menos 100 elementos. No momento em que você inserir o 100º elemento, o array interno se expandirá 6 vezes , transferindo todos os elementos 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 (de acordo com a fórmula (tamanho do Old Array * 1,5) + 1)

Naturalmente, isto é bastante caro em termos de recursos. Portanto, se você já conhece algum número (pelo menos aproximado) de elementos armazenados, é melhor criar imediatamente uma lista com um array de um determinado tamanho:

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

Agora um array de 100 elementos será alocado imediatamente na memória, o que será mais eficiente porque não serão desperdiçados recursos na expansão. Há também o outro lado da moeda. Quando os objetos são removidos da ArrayListmatriz interna, o tamanho não é reduzido automaticamente. Por exemplo, temos ArrayListum array interno de 88 elementos, que está completamente preenchido: Durante a operação do programa, removemos 77 elementos dele, e apenas 11 permanecem nele: Você já adivinhou qual é o problema? Uso ineficiente de memória, é claro! Usamos apenas 11 células, mas temos memória alocada para 88 elementos - isso é 8 vezes mais do que precisamos! Para realizar a otimização neste caso, você pode usar um método de classe especial ArrayList- trimToSize(). Ele “corta” o comprimento do array interno de acordo com o número de elementos atualmente armazenados nele. Agora é alocada tanta memória quanto necessário! :)