Java ArrayList en imágenes

¡Hola! La conferencia de hoy ArrayListserá, por un lado, más sencilla y, por otro, más difícil que las anteriores. Es más difícil, porque hoy miraremos "debajo del capó" ArrayListy estudiaremos lo que le sucede durante las operaciones. Por otro lado, en esta conferencia casi no habrá código, principalmente imágenes y explicaciones. Entonces, vamos :) Como ya sabes, dentro ArrayListde 'a hay una matriz ordinaria, que actúa como un almacén de datos. En la mayoría de los casos, no especificamos el tamaño exacto de la lista. ¡Pero la matriz interna debe tener algún tamaño! Esto es cierto. Su tamaño predeterminado es [10] .

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

Primero, veamos cómo se ve agregar un nuevo elemento. En primer lugar, se comprueba si hay suficiente espacio en la matriz interna y si cabe un elemento más. Si hay espacio, el nuevo elemento se agrega al final de la lista. Cuando decimos "hasta el final", no nos referimos a la última celda de la matriz (eso sería extraño). Esto se refiere a la celda al lado del último elemento actual. Su índice será igual a cars.size(). Nuestra lista está actualmente vacía ( cars.size() = 0). En consecuencia, se agregará un nuevo elemento a la celda con índice 0.

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

Todo está claro aquí. ¿Qué pasará si la inserción se realiza en el medio, es decir, entre varios 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, которая уже занята
}

Nuevamente, primero verifica si hay suficiente espacio en la matriz. Si hay suficiente espacio, los elementos se desplazan hacia la derecha a partir de la celda donde insertamos el nuevo elemento. Pegamos en la celda con índice 1. Es decir, el elemento de la celda 3 se copia a la celda 4, el elemento 2 a la celda 3, el elemento 1 a la celda 2. Después de eso, nuestro nuevo elemento se pega en su lugar. El elemento anterior ( bugatti) ya se ha copiado desde allí a una nueva ubicación. Ahora averigüemos cómo sucedería este proceso si no hubiera espacio para la inserción en la matriz. Por supuesto, primero se comprueba si hay suficiente espacio. Si resulta que no hay suficiente espacio, ArrayListse crea una nueva matriz de tamaño (tamaño de OldArray * 1.5) + 1 dentro de 'a. En nuestro caso, la nueva matriz tendrá un tamaño de 16 celdas. Todos los elementos actuales se copiarán allí inmediatamente. El recolector de basura eliminará la matriz anterior y solo quedará la nueva ampliada. Ahora hay espacio libre para el nuevo elemento. Lo pegamos en la celda 3, que está ocupada. Ahora comienza el procedimiento familiar. Todos los elementos que comienzan en el índice 3 se desplazan una celda hacia la derecha y se agrega silenciosamente un nuevo elemento. ¡Y ahora la inserción es exitosa! Resolvimos la inserción. Ahora hablemos de eliminar elementos . Como recuerdas, cuando trabajamos con matrices, nos encontramos con un problema: cuando las eliminamos, quedaban "agujeros". La única solución era desplazar los elementos hacia la izquierda cada vez que se eliminaban, y usted mismo tenía que escribir el código para el desplazamiento. ArrayListFunciona según el mismo principio, pero en él este mecanismo ya se implementa automáticamente. Esto es lo que parece: Y al final obtenemos el resultado deseado: El elemento lambose eliminó correctamente. Aquí hicimos una eliminación desde el medio. Está claro que eliminar desde el final de la lista será más rápido, ya que el elemento deseado se elimina sin desplazar a todos los demás. Echemos otro vistazo al tamaño de la matriz interna y su almacenamiento en memoria. La expansión de la matriz es un proceso que requiere una cierta cantidad de recursos. Por lo tanto, no debes crear ArrayListcon el tamaño predeterminado si sabes con seguridad que tendrá al menos 100 elementos. Cuando llegue a insertar el elemento número 100, la matriz interna se expandirá 6 veces , transfiriendo cada vez todos los elementos.

• de 10 elementos a 16
• de 16 elementos a 25
• de 25 a 38
• de 38 a 58
• de 58 a 88
• de 88 a 133 (según la fórmula (tamaño del Old Array * 1.5) + 1)

Naturalmente, esto es bastante caro en términos de recursos. Por lo tanto, si ya conoce una cantidad (al menos aproximada) de elementos almacenados, es mejor crear inmediatamente una lista con una matriz de cierto tamaño:

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

Ahora se asignará inmediatamente una matriz de 100 elementos en la memoria, lo que será más eficiente porque no se desperdiciarán recursos en la expansión. También está la otra cara de la moneda. Cuando se eliminan objetos de ArrayListla matriz interna, el tamaño no se reduce automáticamente. Por ejemplo, tenemos ArrayListuna matriz interna de 88 elementos, que está completamente llena: Durante el funcionamiento del programa, eliminamos de ella 77 elementos y solo quedan 11 en ella: ¿ Ya has adivinado cuál es el problema? ¡Uso ineficiente de la memoria, por supuesto! Usamos solo 11 celdas, mientras que tenemos memoria asignada para 88 elementos, ¡eso es 8 veces más de lo que necesitamos! Para realizar la optimización en este caso, puede utilizar un método de clase especial ArrayList: trimToSize(). "Recorta" la longitud de la matriz interna al número de elementos actualmente almacenados en ella. ¡Ahora se asigna tanta memoria como sea necesaria! :)