Matrices dinámicas en Java

Al crear programas de distintos grados de complejidad, cada desarrollador utiliza muchos tipos de datos, incluidas matrices. Esta estructura es muy adecuada para almacenar un conjunto de un tipo, proporciona un gran rendimiento y, en general, es conveniente. Una desventaja importante de las matrices es que son estáticas: su tamaño debe especificarse de antemano. Sin embargo, los programadores aún no saben cómo predecir el futuro (a menos, por supuesto, que aparezca una IA que procese información increíblemente rápido y pueda predecir cualquier evento). Por esta razón, creamos una estructura que puede cambiar su tamaño mientras el programa se ejecuta. Se llama matriz dinámica .

Arreglos dinámicos en el curso JavaRush

Este tema se trata de manera muy inteligible y clara en el nivel 7 y parcialmente en el nivel 8 del curso JavaRush en la búsqueda de Sintaxis de Java. A lo largo de varias conferencias y hasta 18 problemas, se tratan cuestiones clave, los tipos de matrices dinámicas y la diferencia entre ellas, incluido el rendimiento. Este tema es extremadamente importante, ya que las matrices dinámicas alivian al desarrollador de la depresión, los dolores de cabeza y le ahorran una increíble cantidad de tiempo.

¿Qué es una matriz dinámica?

Una matriz dinámica es una matriz que puede cambiar su tamaño durante la ejecución del programa. En Java, esta función la desempeñan principalmente las clases ArrayList y LinkedList. A diferencia de las matrices, ArrayList y LinkedList solo contienen tipos de datos de referencia, es decir, solo pueden almacenar objetos. Afortunadamente, Java tiene mecanismos de autoboxing y autounboxing que le permiten almacenar tipos primitivos en matrices dinámicas. Al igual que una matriz estática, una matriz dinámica es homogénea, es decir, puede almacenar un único tipo de datos. Sin embargo, gracias al mecanismo de herencia y al uso adecuado de las interfaces, es posible almacenar en una matriz dinámica toda una gama de clases diferentes que se heredan de una común, pero hablaremos de eso más adelante. Es decir, una matriz estática funciona así: Y una matriz dinámica en Java funcionará de la siguiente manera (continuando con el diagrama del tercer paso): Java usa una función nativa especial para copiar una matriz, por lo que tal "movimiento" no es muy caro.

¿Por qué necesitamos una matriz dinámica?

Una matriz dinámica en Java se utiliza para procesar conjuntos de datos homogéneos cuyo tamaño se desconoce en el momento en que se escribe el programa. Por ejemplo, es posible que desee almacenar en caché los datos de cada cliente que esté utilizando actualmente la aplicación. Es imposible predecir de antemano el número de estos clientes. Sin matrices dinámicas, este problema se puede solucionar con las siguientes opciones:

1. Cree una gran variedad que tenga 100% de probabilidad de cubrir la necesidad;
2. Cree una matriz estática que actuará como un búfer;
3. Aplicar otras estructuras dinámicas, como conjuntos.

La primera opción es adecuada sólo en el caso de una gama estrictamente limitada. En otros casos, dicha matriz ocupará una gran cantidad de espacio de memoria, lo cual es extremadamente ineficiente. El segundo requerirá la implementación de mecanismos adicionales para borrar, leer, etc. El tercero también tiene desventajas debido a diferencias de funcionalidad.

¿Qué hace una matriz dinámica en Java?

En el lenguaje Java, las clases ArrayList y LinkedList actúan como una matriz dinámica. El más utilizado es ArrayList, ya que actúa como una matriz clásica, a diferencia de LinkedList, que implementa el concepto de lista doblemente enlazada. Hablaremos de ello un poco más tarde.

ArrayList, LinkedList: conceptos y reglas operativas

ArrayList es una matriz clásica que se puede expandir durante la ejecución del programa. Se basa en una matriz normal: su tamaño en el momento de su creación es de 10 elementos. A medida que aumenta el tamaño, aumenta la capacidad. Las reglas por las que funciona ArrayList:

• Al igual que una matriz estática, está indexada desde 0;
• La inserción al final y el acceso por índice son muy rápidos - O(1);
• Para insertar un elemento al principio o en el medio, deberá copiar todos los elementos una celda a la derecha y luego pegar un nuevo elemento en la posición requerida;
• El acceso por valor depende de la cantidad de elementos - O(n);
• A diferencia de una matriz clásica, puede almacenar valores nulos;

En el caso de LinkedList todo es un poco más complicado: se basa en una lista doblemente enlazada. Es decir, estructuralmente, esta matriz dinámica de Java es una serie de objetos dispersos que se refieren entre sí. Es más fácil de explicar con imágenes. Dentro de LinkedList tenemos un objeto principal Head, que almacena información sobre el número de elementos, así como un enlace al primer y último elemento: Ahora el campo size = 0es firsty last = null. Cada elemento que se agrega a esta lista es el contenido de un objeto interno independiente. Agreguemos un elemento Johnny: ahora tenemos un nodo con el valor "Johnny". Para el elemento principal, los enlaces al primer y último elemento apuntan al nuevo nodo. Este objeto también tiene enlaces a los elementos anterior y siguiente. El enlace al anterior siempre será nulo, ya que este es el primer elemento, y el enlace al siguiente siempre será nulo, porque aún no existe. Arreglemos esto: Se agregó un nuevo elemento con el valor “Watson”, que pasó a ser el segundo. Tenga en cuenta que el primer elemento tiene un campo nextque apunta al siguiente elemento y el nuevo elemento tiene un campo previousque apunta al anterior. Para el elemento principal, el enlace al último elemento ahora apunta al nuevo nodo. El siguiente diagrama muestra cómo agregar elementos al medio de la lista: Se ha agregado un nuevo elemento "Hamish". Para insertarlo en el medio de la lista, simplemente reasigne los enlaces a los elementos, como se muestra en la figura. Estas ilustraciones explican el proceso de una lista doblemente enlazada en el nivel superior, sin entrar en detalles. Para resumir la historia sobre LinkedList, podemos derivar varias reglas para su funcionamiento:

• Al igual que una matriz, está indexada desde 0;
• El acceso al primer y último elemento no depende del número de elementos - O(1);
• Obtener un elemento por índice, insertarlo o eliminarlo del medio de una lista depende de la cantidad de elementos: O(n);
• Puede utilizar el mecanismo iterador: luego la inserción y eliminación se producirán en tiempo constante;
• A diferencia de una matriz clásica, puede almacenar valores nulos.

Ejemplos de código

Veamos algunos ejemplos. Los fragmentos de código incluyen ejemplos tanto para ArrayList como para LinkedList.

Creación

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

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

Agregar un 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

A primera vista, los métodos add()AND addLast()realizan la misma funcionalidad, pero el método add()llegó a LinkedList desde la interfaz Listy el método addLastvino desde la interfaz Deque. LinkedList implementa ambas interfaces. Una buena práctica en este caso sería utilizar el método que sea más apropiado para el contexto. Si LinkedList se usa como cola, entonces es mejor usar el archivo addLast. Si LinkedList se usa como lista, sería apropiado usar add().

Eliminando un elemento

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

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

Si un objeto se elimina por índice, el método devuelve el objeto eliminado. Si un objeto se elimina por valor (o se eliminan el primer o último elemento de una LinkedList), el método devuelve verdadero si el objeto se encuentra y elimina; falso en caso contrario.

Acceder a un elemento y buscar en la lista

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

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

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

Caminando en bucle

// Использование обычного цикла
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);
}

Aquí vale la pena decir algunas palabras sobre la búsqueda. Muchos desarrolladores novatos, cuando buscan un elemento en una lista, comienzan la búsqueda en un bucle, comparando todos los elementos con el buscado, a pesar de la presencia de métodos indexOf()y lastIndexOf(). También puedes usar el método contains()para obtener el hecho de que un elemento está en la lista:

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

Enlaces para lectura adicional

1. Aquí hay un artículo excelente sobre cómo eliminar elementos de una ArrayList. Debido al hecho de que se trata de una matriz Java dinámica , existen muchas sutilezas a la hora de eliminar elementos.
2. El funcionamiento de ArrayList se ilustra en detalle aquí .
3. Un poco más sobre LinkedList.
4. Un par de artículos de Habr sobre ArrayList y LinkedList .