Análise detalhada da classe ArrayList [Parte 1]

Este artigo examinará detalhadamente a classe ArrayList do Collections Framework, que talvez seja a mais fácil de entender, devido ao fato de ser baseada em um array regular. É quase certo que você fará uma pergunta sobre esta classe e sua implementação em Java na entrevista. Na segunda parte analisaremos os métodos restantes e escreveremos nossa própria implementação de um array dinâmico para números. A classe ArrayList herda da classe AbstractList e implementa as seguintes interfaces: List, RandomAccess, Cloneable, Serializable. Uma análise detalhada da classe ArrayList [Parte 2] A classe ArrayList oferece suporte a arrays dinâmicos que podem ser expandidos conforme necessário. Sua necessidade e eficácia são explicadas pelo fato de um array regular ter um comprimento fixo: uma vez criado, não pode aumentar ou diminuir, o que impõe restrições caso não se saiba o tamanho do array necessário. Essencialmente, a classe ArrayList é uma lista de matrizes de comprimento variável de referências de objetos. É importante entender que o tamanho (número de células) do array interno não diminui automaticamente quando elementos são removidos dele. Na verdade, o valor da variável size, que indica o número de elementos realmente presentes no array, é diminuído. Digamos que criamos um novo objeto da classe ArrayList e adicionamos 5 elementos a ele. Por padrão, uma matriz de 10 elementos é criada. Neste caso, a chamada capacidade (tamanho/volume) do nosso objeto será igual a 10, mas o valor da variável sizeserá igual a cinco. E quando excluímos elementos, vemos alterações no valor da variável size, pois .lengthnão podemos acessar o array interno da classe ArrayList e descobrir seu comprimento. O tamanho pode ser reduzido usando um método adicional trimToSize(), que será discutido abaixo. Vejamos os campos da classe.

• Campo responsável pelo volume padrão do array dinâmico:

  private static final int DEFAULT_CAPACITY = 10

  Ao criar um novo objeto new ArrayList<>() (construtor sem parâmetros), um array de 10 elementos é criado dentro dele.

• Um campo no qual todos os elementos da coleção são armazenados:

  transient Object[] elementData

  Marcado com uma palavra-chave transient- o campo não é gravado no fluxo de bytes ao usar o algoritmo de serialização padrão. Vale ressaltar que o campo não está marcado com a palavra-chave private, mas isso foi feito para facilitar o acesso a este campo a partir de classes aninhadas (por exemplo, SubList).

• Um campo de contador que armazena o número de elementos realmente na matriz:

  private int size

  O valor é incrementado/decrementado ao executar operações como inserção e exclusão.

Existem mais 3 campos na classe, mas essencialmente são adicionais, portanto não faz sentido considerá-los. A classe possui três construtores:

1. public ArrayList()– cria uma matriz de lista vazia de 10 elementos;
2. public ArrayList(Collection < ? extends E > c)– cria um array de lista inicializado com elementos da coleção passada (se quisermos criar um novo ArrayList baseado em alguma coleção);
3. public ArrayList(int initialCapacity)– cria um array de lista com capacidade inicial. Se o parâmetro passado inicialCapacity for maior que 0, então uma matriz do tamanho especificado é criada (ao campo interno elementData é atribuído um link para uma nova matriz do tipo Object de tamanho inicialCapacity). Se o parâmetro for 0, um array vazio será criado. Se o parâmetro especificado for menor que 0, uma IllegalArgumentException será lançada.

Criando um objeto

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

O objeto recém-criado listcontém propriedades (campos) elementDatae arquivos size. Um armazenamento de valor elementDatanada mais é do que um array de um tipo específico (especificado em genérico – <>), no nosso caso String[]. Se um construtor sem parâmetros for chamado, então, por padrão, um array de 10 elementos do tipo Object será criado (com uma conversão para o tipo, é claro). Adicionando elementos Classicamente, adicionar elementos a uma matriz de lista é feito usando variantes sobrecarregadas do add().

public boolean add(E элемент)

Bem, vamos acrescentar: list.add("0"); Dentro deste método, é chamada uma versão sobrecarregada do método add(), marcada como private, que por sua vez recebe três parâmetros como entrada: o elemento a ser adicionado, o array interno e seu tamanho. No método privado, ocorre uma verificação: se o parâmetro de tamanho passado for igual ao comprimento do array interno (ou seja, o array está cheio), então o array recebe o resultado do método grow(int minCapacity)(o valor atual do campo size + 1 é passado para o método, pois é necessário levar em consideração o elemento que está sendo adicionado), no qual o interno o array recebe um link para o novo array criado obtido pela cópia dos elementos do array original:

Arrays.copyOf(elementData, newCapacity(minCapacity))

Como segundo parâmetro do método, copyOfindicamos o resultado do método newCapacity(int minCapacity), dentro do qual o novo tamanho do array é calculado. É calculado usando a seguinte fórmula: int newCapacity = oldCapacity + (oldCapacity >> 1) Para uma matriz com o tamanho padrão, o seguinte será verdadeiro: >> 1– deslocamento bit a bit para a direita em um (um operador que reduz um número à metade). Essencialmente, significa dividir por 2 elevado a 1. Acontece que dividimos 10 por 2 e adicionamos 10. Total, a nova capacidade do array é 15, mas como estamos adicionando o 11º elemento, então 15 + 1 = 16. Voltemos à nossa lista e suponhamos que já adicionamos 10 elementos a ela e tentamos adicionar 11. A verificação mostrará que não há espaço no array. Assim, um novo array é criado e chamado Arrays.copyOf, que utiliza internamente o método do sistema System.arraycopy(). Ou aqui está um exemplo claro de um artigo sobre JavaRush: Depois de todas essas verificações e aumentando o tamanho do array se necessário, então em um método privado add()um novo elemento é adicionado ao final do array, e o parâmetro atual sizeé aumentado em um . A matriz antiga será posteriormente processada pelo coletor de lixo. É assim que funciona um array dinâmico: quando adicionamos elementos, verificamos se ainda há espaço nele. Se houver espaço, simplesmente adicionamos o elemento ao final do array. O final não significa a última célula do array, mas sim a célula que corresponde ao valor size. Adicionamos o primeiro elemento ao array; ele é colocado na célula com índice [0]. O valor do campo sizeaumentou em um e = 1. Adicionamos o próximo elemento: vemos que size = 1, respectivamente, colocamos o elemento na célula com índice [1] e assim por diante. Existe uma versão sobrecarregada do método com dois parâmetros:

public void add(int index, E element)

Podemos especificar a posição (índice) da célula onde queremos adicionar o elemento. Primeiramente, é verificada a exatidão do valor do índice especificado, pois existe a possibilidade de ser especificado um índice incorreto, que apontará para uma célula onde não há nada, ou que simplesmente não existe. Verificando índices: index > size || index < 0– se o índice especificado for maior que o tamanho atual do array ou for menor que 0, uma exceção será lançada IndexOutOfBoundsException. Então, se necessário, o tamanho do array é aumentado, semelhante ao exemplo acima. Você provavelmente já ouviu falar que durante operações de adição/remoção em um array, algo é deslocado em algum lugar (para a direita ou para a esquerda). Assim, o deslocamento é realizado copiando o array: System.arraycopy(elementData, index, elementData, index + 1, s - index); Todos os elementos localizados à direita do índice especificado serão deslocados uma posição para a direita (índice+1). E só depois disso um novo elemento é adicionado ao array interno no índice especificado. Como deslocamos parte do array para a direita em um (um novo array não é criado), a célula que precisamos estará livre para gravação. O link para o array antigo é apagado e no futuro será assumido pelo coletor de lixo. Cole “maserati” na célula [3], que já está ocupada: Assim, quando um elemento é inserido no índice e não há espaços livres no array, a chamada System.arraycopy()acontecerá duas vezes: a primeira in grow(), a segunda no próprio método add(index, value), o que afetará claramente a velocidade de toda a operação de adição. Como resultado, quando é necessário escrever outro elemento no array interno, mas não há espaço lá, então é isso que acontece dentro do ArrayList:

• Um novo array é criado com tamanho 1,5 vezes maior que o original, mais um elemento.
• Todos os elementos do array antigo são copiados para o novo array
• O novo array é armazenado na variável interna do objeto ArrayList e o array antigo é declarado lixo.

A capacidade dos objetos do tipo ArrayList pode ser aumentada manualmente usando o método:

public void ensureCapacity(int minCapacity)

Ao aumentar a capacidade do array antecipadamente, você pode evitar a redistribuição adicional de RAM posteriormente. O método aumenta o tamanho do array interno para acomodar o número de elementos passados minCapacity. O método ensureCapacity()não afeta o campo size, afeta o capacity(tamanho) do array interno. Mais uma vez enfatizo que sizeambas são capacitycoisas diferentes e é muito importante não confundi-las! Se você quiser reduzir o tamanho do array subjacente a partir do qual o ArrayList é construído para o número atual de elementos realmente armazenados, você deve chamar o método trimToSize(). Após retirar os elementos da coleção, size()ele mostrará a quantidade de elementos realmente existentes, e capacitynão diminuirá! Suponha: inserimos 100 elementos, excluímos os primeiros 50, sizeficará igual a 50, e assim capacitypermanecerá 100. Para reduzir e capacity, precisamos usar o método trimToSize(), que ajusta toda a nossa capacidade ao tamanho atual. Como isso se encaixa? Copia nosso array para que não haja mais células vazias (o comprimento do novo array é simplesmente igual ao campo de tamanho). Você também pode adicionar elementos à nossa coleção usando o arquivo addAll.

public boolean addAll(Collection< ? extends E> c)
public boolean addAll(int index, Collection< ? extends E> collection);

A primeira opção permite adicionar todos os elementos da coleção especificada no parâmetro do método (por exemplo, outra planilha) à coleção original (inserir no final) para a qual foi feita a chamada do método. A coleção passada (também pode ser um conjunto) é convertida em um array usando o método toArray(). Naturalmente, a operação de adição também é realizada por meio de cópia. A segunda é adicionar todos os elementos collectionà lista, começando pelo index index. Neste caso, todos os elementos serão deslocados para a direita de acordo com o número de elementos da lista collection. Removendo elementos Primeiro, vejamos as opções clássicas para remover elementos de um ArrayList.

public E remove(int index)

Executa a exclusão por índice e desloca todos os elementos subsequentes (após o elemento no índice especificado) para a esquerda, fechando assim os “buracos”. Também retorna o elemento excluído (E), que é previamente gravado em uma variável adicional antes da exclusão, cujo valor obtemos como resultado da chamada do método. Para entender o que é E, você precisará se familiarizar com os chamados tipos genéricos. A notação E indica que o método retorna o tipo de dados que foi especificado ao criar o objeto ArrayList (lembre-se: List <String> list, portanto, neste caso, E será “substituído” String). Para uma compreensão geral, recomendo fortemente que você se familiarize com os tipos genéricos. A exatidão do índice inserido é verificada e, dentro do método, o elemento não é completamente excluído, mas é chamado um método privado fastRemove(Object[] es, int i), no qual a exclusão já ocorre. Passamos nosso array e o índice especificado para o método como entrada. Os elementos são copiados usando System.arraycopy(), o tamanho do array é reduzido e então atribuímos nulo ao último elemento. É importante notar que um novo array não é criado: System.arraycopy(es, i + 1, es, i, size - 1 - i); a parte que está à direita da posição sob o índice especificado (i+1) é copiada em nosso(s) array(s) original(es) e está localizada a partir da própria posição (i) onde estava localizado o elemento a ser excluído. Assim, realizamos um deslocamento para a esquerda e apagamos nosso elemento. Vamos tentar remover o elemento do índice 3 do array abaixo: Consideremos a segunda versão do método:

public boolean remove(Object o)

O método remove o elemento passado da lista oou, mais precisamente, o objeto no link especificado. Se um elemento estiver presente na lista, ele será removido e todos os elementos serão deslocados para a esquerda. Se o elemento existir na lista e for removido com sucesso, o método retornará verdadeiro; caso contrário, falso. Semelhante à opção de exclusão por índice, o método é chamado fastRemove(), onde ocorrem exatamente as mesmas ações. A diferença é que o método remove(Object o)busca adicionalmente o objeto desejado através de um método equals()da classe Object. Ao remover por valor, o loop percorre todos os elementos da lista até encontrar uma correspondência. Apenas o primeiro elemento encontrado será excluído. Para resumir: ao excluir elementos de um array dinâmico, não restam lacunas como em um array normal (a célula excluída não ficará vazia). Todos os elementos subsequentes (que estavam à direita do índice) são deslocados uma posição para a esquerda. Existem vários métodos adicionais que podem ser usados ​​para remover elementos da lista em graus variados. Vamos examiná-los brevemente. Limpando nossa coleção:

public void clear()

Um loop simples foritera por todos os elementos de uma matriz, atribuindo nulo a cada elemento. Você pode remover da nossa coleção os elementos que estão contidos em outra coleção transferida como esta:

public boolean removeAll(Collection< ?> c)

Se você precisar remover vários elementos, provavelmente não deveria fazer isso em um loop condicional: é mais conveniente e seguro usar o método removeAll(). Aceita uma coleção de elementos que serão removidos da lista. A coleção deve conter elementos do mesmo tipo que a lista de destino armazena. Caso contrário, será jogado fora ClassCastException. O método retornará verdadeiro se a lista tiver sido alterada como resultado da chamada do método. Remove elementos que não pertencem à coleção passada:

public boolean retainAll(Collection< ?> c)

Digamos que temos uma coleção:

List< String> listFirst = new ArrayList<>();
listFirst.add("White");
listFirst.add("Black");
listFirst.add("Red");

E o segundo:

List< String> listSecond = new ArrayList<>();
listSecond.add("Green");
listSecond.add("Red");
listSecond.add("White");

Então depois de listSecond.retainAll(listFirst)permanecerá listSecond:

"White"
"Red"

Já que "Verde" foi removido, o que não está no formato listFirst. Mas depois listSecond.removeAll(listFirst)disso listSecondpermanecerá:

"Green"
Удалorсь все элементы, которые есть в listFirst.

Não pertencer à coleção passada - significa que se houver elementos que não estão na coleção passada, será necessário removê-los da primeira (à qual o método é aplicado). Pertencente à coleção transferida - portanto, se houver um elemento na primeira e na segunda coleção (transferida), a duplicata da primeira será destruída.

protected void removeRange(int fromIndex, int toIndex)

Remove da lista todos os elementos que estão entre o índice inicial especificado (inclusivo) e o índice final especificado (não inclusivo). É importante notar que o método não pode ser chamado diretamente em um objeto ArrayList. Para usá-lo você precisa herdar de AbstractList/ArrayList. O método também é usado por outro método (subList, que será discutido mais adiante).

public boolean removeIf(Predicate< ? super E> filter)

Remove elementos de uma coleção com base em um determinado predicado. O próprio predicado é uma determinada função/algoritmo/condição com base na qual um ou mais elementos correspondentes a uma determinada condição serão removidos. Predicate— uma interface funcional (contém apenas um método, portanto pode ser usada como lambda), funciona segundo o princípio “recebeu um parâmetro - retornou booleano”. Essencialmente, o método substitui a implementação da interface Collectione implementa a seguinte “estratégia”: itera pelos elementos e marca aqueles que correspondem ao nosso Predicate; em seguida, ele é executado uma segunda vez para remover (e deslocar) os elementos que foram marcados na primeira iteração. Vamos implementar uma interface Predicateque retornará true se dois objetos forem iguais:

class SamplePredicate< T> implements Predicate< T>{
  T varc1;
  public boolean test(T varc){
     if(varc1.equals(varc)){
       return true;
  }
  return false;
  }
}

Em outra classe, vamos criar um ArrayList Stringe um objeto da nossa classe que implementa Predicate:

ArrayList< String> color_list = new ArrayList<> ();
SamplePredicate< String> filter = new SamplePredicate<> ();

varc1Vamos escrever o valor "Branco" na variável :

filter.varc1 = "White";

Vamos adicionar algumas linhas à lista:

color_list.add("White");
color_list.add("Black");
color_list.add("Red");
color_list.add("White");
color_list.add("Yellow");
color_list.add("White");

Vamos executar o método da lista removeIf, para o qual passaremos nosso objeto com a condição:

color_list.removeIf(filter);

Como resultado, todas as linhas com o valor "Branco" serão removidas da lista, pois nosso "predicado" as compara quanto à igualdade. Lista final: [Preto, Vermelho, Amarelo]. Substituindo elementos

public E set(int index, E element)

Substitui o elemento na posição especificada indexpelo passado element. O índice também deve ser maior que zero e menor que o índice do último elemento, caso contrário será lançada uma exceção IndexOutOfBoundsException. Nenhuma cópia da matriz interna ocorre. Simplesmente, em vez do elemento no índice especificado, um novo elemento é inserido, ou seja, sobrescrever o valor.

public void replaceAll(UnaryOperator<e> operator)

Altera todos os elementos da coleção (possível com uma condição). Geralmente usado em combinação com lambdas ou uma classe anônima (mas para maior clareza, no exemplo usaremos simplesmente uma classe que implementa a interface) que implementa a interface UnaryOperatore define seus métodos. Vamos implementar a interface:

class MyOperator< T> implements UnaryOperator< T>{
   T varc1;
   public T apply(T varc){
     return varc1;
  }
}

Em outra classe, vamos criar um ArrayList Stringe um objeto da nossa classe que implementa UnaryOperator:

ArrayList< String> color_list = new ArrayList<> ();
MyOperator< String> operator = new MyOperator<> ();

varc1Vamos escrever o valor "Branco" na variável :

operator.varc1 = "White";

Vamos adicionar algumas linhas à lista:

color_list.add("White");
color_list.add("Black");
color_list.add("Red");
color_list.add("White");
color_list.add("Yellow");
color_list.add("White");

Vamos executar um método da lista replaceAllpara o qual passaremos nosso objeto operator:

color_list.replaceAll(operator);

Como resultado, todos os valores da lista foram substituídos por “Branco”: [Branco, Branco, Branco, Branco, Branco, Branco]. E é assim que, por exemplo, você pode remover todos os espaços das strings que estão na coleção:

ArrayList< String> list = new ArrayList<>(Arrays.asList("A   ", "  B  ", "C"));
list.replaceAll(String::trim);

Outros métodos: Você pode converter um ArrayList em um array regular usando o método:

public Object[] toArray()

ou

public < T> T[] toArray(T[] a)

- aqui o tipo do array retornado é determinado em runtime Este método permitirá:

1. acelerar algumas operações;
2. passar um array como parâmetro para um método que não esteja sobrecarregado para aceitar a coleção diretamente;
3. Integração de novo código baseado em coleção com código legado que não reconhece coleções.

Retorne um objeto de cópia do array:

public Object clone()

Observe que o método clone()retorna o tipo Object, portanto, após chamá-lo, você precisará converter para a classe necessária. A clonagem cria um novo objeto independente. Verifique a coleção quanto à presença de um objeto:

public boolean contains(Object o)

Verifica a presença de um objeto na lista (internamente usando o método equals da classe Object, ou seja, compara referências), retorna verdadeiro/falso dependendo do resultado. Além dos loops usuais, você pode iterar (acessar cada elemento, bem como executar alguma ação) uma coleção usando:

public void forEach(Consumer< ? super E> action)

É assim que podemos exibir nossa lista:

List< Integer> numbers = new ArrayList<>(Arrays.asList(10, 20, 50, 100, -5));
numbers.forEach((number)-> System.out.println(number));

Sem usar lambdas você precisa usar uma classe anônima e substituir o método acceptde interface Consumer:

numbers.forEach(new Consumer< Integer>() {
  @Override
   public void accept(Integer integer) {
      System.out.println(integer);
          }
});

Obtenha um elemento pelo seu índice:

public E get(int index)

Usado para acesso aleatório aos elementos da coleção. Retorna o elemento localizado na lista no índice especificado. Se index < 0ou for index >=o número máximo de elementos na lista, uma exceção será lançada IndexOutOfBoundsException. Este é o método básico de recuperação de um elemento de uma lista, e o tempo para recuperar um elemento por índice será sempre o mesmo, independente do tamanho do ArrayList, pois ele está acessando uma célula específica do array. Encontrando índices para objetos especificados:

public int indexOf(Object o);
public int lastIndexOf(Object o);

Os métodos retornam o índice do primeiro (quando o objeto fornecido é encontrado pela primeira vez) ou da última ocorrência (quando o objeto fornecido é encontrado pela última vez) elemento na lista. Se o elemento não existir na lista, os métodos retornarão -1. Verifique a coleção em busca de elementos:

public boolean isEmpty();

O método retorna verdadeiro se a lista estiver vazia (procura se o campo é igual size 0), caso contrário, falso. Se a lista contiver apenas elementos nulos, o método retornará falso. Em outras palavras, os elementos nulos também são levados em consideração por este método. Descubra o número de elementos em uma lista:

public int size();

Retorna o número de elementos na lista (valores do campo de tamanho). O número de elementos pode diferir da capacidade (capacidade) da lista. Obtenha um iterador para uma lista:

public Iterator< E> iterator();

Retorna um iterador para uma lista para uso posterior em um loop ou qualquer outro processamento. O iterador implementa comportamento fail-fast. Se ele percorrer a coleção e notar algumas modificações nela (que não foram obtidas usando os métodos iteradores), ele imediatamente lançará uma exceção ConcurrentModificationException. Um iterador tem algo chamado modification count. Quando o iterador percorre a coleção após each next/hasNext/remove, ele verifica esse contador. Se não corresponder ao que o iterador esperava ver, ele lançará uma exceção. Não considerarei iteradores em detalhes aqui.

public ListIterator< E> listIterator() и public ListIterator< E> listIterator(int index)

Retorna um iterador de lista para uso posterior em um loop ou qualquer outro processamento. A interface ListIteratorestende a interface Iteratorpara travessia bidirecional da lista e modificação de seus elementos. Na versão sobrecarregada, você pode passar o índice a partir do qual a “travessia” começará. O índice, neste caso, denota o primeiro elemento a partir do qual o método iniciará seu trabalho next()e, quando o método for chamado, previous()o percurso começará a partir do elemento sob o índice “índice passado - 1”.

public Spliterator <E> spliterator()

Java 8 introduz um novo tipo de ligação tardia e iterador rápido contra falhas chamado iterador delimitador. Os iteradores separadores permitem iterar sobre uma sequência de elementos, mas são usados ​​de uma maneira diferente. A característica mais importante da interface Spliterator é sua capacidade de suportar iteração paralela de partes individuais de uma sequência de elementos e, portanto, programação paralela.