Matrizes Dinâmicas em Java

Ao criar programas de vários graus de complexidade, cada desenvolvedor usa vários tipos de dados, incluindo arrays. Essa estrutura é adequada para armazenar um conjunto de um tipo, oferece ótimo desempenho e geralmente é conveniente. Uma desvantagem significativa dos arrays é que eles são estáticos: seu tamanho deve ser especificado antecipadamente. No entanto, os programadores ainda não sabem como prever o futuro (a menos, é claro, que apareça uma IA que processará informações com uma rapidez incrível e será capaz de prever quaisquer eventos). Por isso, criamos uma estrutura que pode mudar de tamanho durante a execução do programa. É chamado de array dinâmico .

Matrizes dinâmicas no curso JavaRush

Este tópico é abordado de forma muito inteligível e clara no nível 7 e parcialmente no nível 8 do curso JavaRush na missão Java Syntax. Ao longo de várias palestras e até 18 problemas, são abordadas questões importantes, tipos de matrizes dinâmicas e a diferença entre elas, incluindo desempenho. Este tópico é extremamente importante, pois os arrays dinâmicos aliviam o desenvolvedor de depressão, dores de cabeça e economizam uma quantidade incrível de tempo.

O que é uma matriz dinâmica?

Um array dinâmico é um array que pode mudar de tamanho durante a execução do programa. Em Java, essa função é desempenhada principalmente pelas classes ArrayList e LinkedList. Ao contrário dos arrays, ArrayList e LinkedList contêm apenas tipos de dados de referência, ou seja, só podem armazenar objetos. Felizmente, Java possui mecanismos de autoboxing e autounboxing que permitem armazenar tipos primitivos em arrays dinâmicos. Assim como um array estático, um array dinâmico é homogêneo, ou seja, pode armazenar um único tipo de dados. No entanto, graças ao mecanismo de herança e ao uso adequado de interfaces, é possível armazenar em um array dinâmico toda uma gama de classes diferentes que são herdadas de uma classe comum, mas falaremos mais sobre isso a seguir. Ou seja, um array estático funciona assim: E um array dinâmico em Java funcionará da seguinte maneira (continuando o diagrama da terceira etapa): Java usa uma função nativa especial para copiar um array, então tal “mudança” não é muito caro.

Por que precisamos de um array dinâmico?

Um array dinâmico em Java é usado para processar conjuntos de dados homogêneos cujo tamanho é desconhecido no momento em que o programa é escrito. Por exemplo, você pode querer armazenar em cache os dados de cada cliente que está usando o aplicativo no momento. É impossível prever antecipadamente o número desses clientes. Sem matrizes dinâmicas, este problema pode ser resolvido com as seguintes opções:

1. Crie um array grande com 100% de probabilidade de cobrir a necessidade;
2. Crie um array estático que funcionará como buffer;
3. Aplique outras estruturas dinâmicas, como conjuntos.

A primeira opção é adequada apenas no caso de um alcance estritamente limitado. Em outros casos, tal array ocupará uma grande quantidade de espaço de memória, o que é extremamente ineficiente. A segunda exigirá a implementação de mecanismos adicionais para limpeza de buffer, leitura e assim por diante. O terceiro também apresenta desvantagens devido a diferenças de funcionalidade.

Qual é a função de um array dinâmico em Java

Na linguagem Java, as classes ArrayList e LinkedList atuam como um array dinâmico. O mais comumente usado é ArrayList, pois atua como um array clássico, ao contrário do LinkedList, que implementa o conceito de lista duplamente vinculada. Falaremos sobre isso um pouco mais tarde.

ArrayList, LinkedList – conceitos e regras de funcionamento

ArrayList é um array clássico que pode ser expandido durante a execução do programa. É baseado em um array regular: seu tamanho quando criado é de 10 elementos. À medida que o tamanho aumenta, a capacidade aumenta. As regras pelas quais ArrayList funciona:

• Assim como um array estático, ele é indexado em 0;
• A inserção no final e o acesso por índice são muito rápidos - O(1);
• Para inserir um elemento no início ou no meio, você precisará copiar todos os elementos uma célula à direita e depois colar um novo elemento na posição desejada;
• O acesso por valor depende da quantidade de elementos - O(n);
• Ao contrário de um array clássico, ele pode armazenar nulos;

No caso do LinkedList tudo é um pouco mais complicado: ele se baseia em uma lista duplamente vinculada. Ou seja, estruturalmente, esse array Java dinâmico é uma série de objetos dispersos que se referem uns aos outros. É mais fácil explicar com fotos. Dentro do LinkedList temos um objeto principal Head, que armazena informações sobre a quantidade de elementos, além de um link para o primeiro e último elementos: Agora o campo size = 0é , firste last = null. Cada elemento adicionado a esta lista é o conteúdo de um objeto interno separado. Vamos adicionar um elemento Johnny: Agora temos um nó com o valor “Johnny”. Para o elemento principal, os links para o primeiro e o último elemento apontam para o novo nó. Este objeto também possui links para os elementos anteriores e seguintes. O link para o anterior será sempre nulo, pois este é o primeiro elemento, e o link para o próximo será sempre nulo, pois ainda não existe. Vamos consertar isso: Adicionado um novo elemento com o valor “Watson”, que passou a ser o segundo. Observe que o primeiro elemento possui um campo nextque aponta para o próximo elemento, e o novo elemento possui um campo previousque aponta para o anterior. Para o elemento principal, o link para o último elemento agora aponta para o novo nó. O diagrama a seguir mostra como adicionar elementos ao meio da lista: Um novo elemento “Hamish” foi adicionado. Para inseri-lo no meio da lista, basta reatribuir os links aos elementos, conforme mostra a figura. Estas ilustrações explicam o processo de uma lista duplamente vinculada no nível superior, sem entrar em detalhes. Para resumir a história do LinkedList, podemos derivar várias regras para seu funcionamento:

• Assim como um array, ele é indexado em 0;
• O acesso ao primeiro e ao último elemento não depende do número de elementos - O(1);
• Obter um elemento por índice, inserir ou excluir do meio de uma lista depende da quantidade de elementos - O(n);
• Você pode usar um mecanismo iterador: então a inserção e a exclusão ocorrerão em tempo constante;
• Ao contrário de um array clássico, ele pode armazenar nulos.

Exemplos de código

Vejamos alguns exemplos. Os trechos de código incluem exemplos para ArrayList e LinkedList.

Criação

// Создаем новый список
ArrayList<String> arrayList = new ArrayList<>();
// Создается новый список и указывается начальный размер внутреннего массива
ArrayList<String> arrayListLarge = new ArrayList<>(100000);

// Создаем новый LinkedList
LinkedList<String> linkedList = new LinkedList<>();

Adicionando um elemento

// Новый элемент добавляется в конец
arrayList.add("Johhny");
// Новый элемент добавляется в указанную позицию (в данном случае — в начало)
arrayList.add(0, "Watson");

// Новый элемент добавляется в конец двусвязного списка
linkedList.add("Java");
// Новый элемент добавляется в нулевую позицию списка:
linkedList.addFirst("I think");
// Новый элемент добавляется в конец списка
linkedList.addLast("language");
// Новый элемент добавляется в указанную позицию
linkedList.add(2, "is a terrific");

// Получение размера списков
int arraySize = arrayList.size(); // 2
int linkedSize = linkedList.size(); // 4

À primeira vista, os métodos add()AND addLast()executam a mesma funcionalidade, mas o método add()veio para LinkedList da interface Liste o método addLastveio da interface Deque. LinkedList implementa ambas as interfaces. Uma boa prática neste caso seria utilizar o método mais adequado ao contexto. Se LinkedList for usado como fila, é melhor usar o arquivo addLast. Se LinkedList for usado como uma lista, seria apropriado usar add().

Removendo um elemento

// Удаление element по индексу
arrayList.remove(0);
// Удаление element по значению
arrayList.remove("Johnny");

// Удаление первого element в списке
linkedList.removeFirst();
// Удаление первого element в списке, фактически вызов предыдущего метода
linkedList.remove();
// Удаление последнего element в списке
linkedList.removeLast();
// Удаление первого вхождения element в список
linkedList.removeFirstOccurrence("language");
// Удаление последнего вхождения element в список
linkedList.removeLastOccurrence("Java");
// Удаление по индексу
linkedList.remove(2);

Se um objeto for excluído por índice, o método retornará o objeto excluído. Se um objeto for excluído por valor (ou o primeiro ou o último elemento de uma LinkedList forem excluídos), o método retornará verdadeiro se o objeto for encontrado e excluído, falso caso contrário.

Acessando um elemento e pesquisando na lista

// Доступ к элементу по индексу
String arrayElement = arrayList.get(2);
// Поиск element по значению
int arrayIndex = arrayList.indexOf("Watson");
// Поиск последнего индекса вхождения element в список
int lastArrayIndex = arrayList.lastIndexOf("Watson");

// Доступ по индексу
String linkedElement = linkedList.get(3);
// Получение первого element
String firstLinkedElement = linkedList.getFirst();
// Получение последнего element
String lastLinkedElement = linkedList.getLast();

// Поиск element по значению
int linkedIndex = linkedList.indexOf("Java");
// Поиск последнего индекса вхождения element в список
int lastLinkedIndex = linkedList.lastIndexOf("Java");

Andando em loop

// Использование обычного цикла
for(int i = 0; i<arrayList.size(); i++) {
  String value = arrayList.get(i);
  System.out.println(value);
}

for(int i = 0; i<linkedList.size(); i++) {
  String value = linkedList.get(i);
  System.out.println(value);
}

// Использование цикла for-each
for(String s : arrayList) {
  System.out.println(s);
}

for(String s : linkedList) {
  System.out.println(s);
}

Aqui vale a pena dizer algumas palavras sobre pesquisa. Muitos desenvolvedores novatos, ao buscar um elemento em uma lista, iniciam a busca em loop, comparando todos os elementos com o buscado, apesar da presença dos métodos indexOf()e lastIndexOf(). Você também pode usar o método contains()para saber que um elemento está na lista:

boolean isContainsSherlock = arrayList.contains("Sherlock");
boolean isContainsPhp = linkedList.contains("Php");

Links para leitura adicional

1. Há um excelente artigo aqui sobre como remover elementos de um ArrayList. Devido ao fato de se tratar de um array Java dinâmico , existem muitas sutilezas na remoção de elementos.
2. O funcionamento do ArrayList é ilustrado em detalhes aqui .
3. Um pouco mais sobre LinkedList.
4. Alguns artigos de Habr sobre ArrayList e LinkedList .