Análisis detallado de la clase ArrayList [Parte 1]

Este artículo analizará detalladamente la clase ArrayList de Collections Framework, que es quizás la más fácil de entender, debido a que se basa en una matriz normal. Es casi seguro que durante la entrevista le harán una pregunta sobre esta clase y su implementación en Java. En la segunda parte analizaremos los métodos restantes y escribiremos nuestra propia implementación de una matriz dinámica para números. La clase ArrayList hereda de la clase AbstractList e implementa las siguientes interfaces: List, RandomAccess, Cloneable, Serializable. Un análisis detallado de la clase ArrayList [Parte 2] La clase ArrayList admite matrices dinámicas que se pueden expandir según sea necesario. Su necesidad y eficacia se explica por el hecho de que una matriz normal tiene una longitud fija: una vez creada, no puede crecer ni encogerse, lo que impone restricciones si no se sabe qué tamaño se necesitará la matriz. Esencialmente, la clase ArrayList es una lista de referencias de objetos de longitud variable. Es importante comprender que el tamaño (número de celdas) de la matriz interna no disminuye automáticamente cuando se eliminan elementos de ella. De hecho, se disminuye el valor de la variable size, que indica el número de elementos realmente presentes en la matriz. Digamos que creamos un nuevo objeto de la clase ArrayList y le agregamos 5 elementos. De forma predeterminada, se crea una matriz de 10 elementos. En este caso, la llamada capacidad (tamaño/volumen) de nuestro objeto será igual a 10, pero el valor de la variable sizeserá igual a cinco. Y cuando eliminamos elementos, vemos cambios en el valor de la variable size, ya que .lengthno podemos acceder al array interno de la clase ArrayList y conocer su longitud. El tamaño se puede reducir utilizando un método adicional trimToSize(), que se analizará a continuación. Veamos los campos de clase.

• Campo responsable del volumen predeterminado de la matriz dinámica:

  private static final int DEFAULT_CAPACITY = 10

  Al crear un nuevo objeto new ArrayList<>() (constructor sin parámetros), se crea una matriz de 10 elementos en su interior.

• Un campo en el que se almacenan todos los elementos de la colección:

  transient Object[] elementData

  Marcado con una palabra clave transient: el campo no se escribe en el flujo de bytes cuando se utiliza el algoritmo de serialización estándar. Vale la pena señalar que el campo no está marcado con la palabra clave private, pero esto se hizo para facilitar el acceso a este campo desde clases anidadas (por ejemplo, SubList).

• Un campo de contador que almacena la cantidad de elementos que realmente hay en la matriz:

  private int size

  El valor aumenta/disminuye al realizar operaciones como inserción y eliminación.

Hay 3 campos más en la clase, pero esencialmente son adicionales, por lo que no tiene sentido considerarlos. La clase tiene tres constructores:

1. public ArrayList()– crea una matriz de lista vacía de 10 elementos;
2. public ArrayList(Collection < ? extends E > c)– crea una matriz de lista inicializada con elementos de la colección pasada (si queremos crear una nueva ArrayList basada en alguna colección);
3. public ArrayList(int initialCapacity)– crea una matriz de lista con una capacidad inicial. Si el parámetro inicialCapacity pasado es mayor que 0, entonces se crea una matriz del tamaño especificado (al campo interno elementData se le asigna un enlace a una nueva matriz de tipo Objeto de tamaño inicialCapacity). Si el parámetro es 0, entonces se crea una matriz vacía. Si el parámetro especificado es menor que 0, se lanza una IllegalArgumentException.

Creando un objeto

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

El objeto recién creado listcontiene propiedades (campos) elementDatay size. Un almacén de valores elementDatano es más que una matriz de un tipo específico (especificado en genérico – <>), en nuestro caso String[]. Si se llama a un constructor sin parámetros, entonces, de forma predeterminada, se creará una matriz de 10 elementos de tipo Objeto (con una conversión al tipo, por supuesto). Agregar elementos Clásicamente, agregar elementos a una matriz de lista se realiza usando variantes sobrecargadas de add().

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

Bueno, agreguemos: list.add("0"); Dentro de este método, se llama a una versión sobrecargada del método add(), marcada como private, que a su vez toma como entrada tres parámetros: el elemento a agregar, el array interno y su tamaño. En el método privado, se produce una verificación: si el parámetro de tamaño pasado es igual a la longitud de la matriz interna (es decir, la matriz está llena), entonces a la matriz se le asigna el resultado del método grow(int minCapacity)(el valor actual del campo Se pasa size + 1 al método, ya que es necesario tener en cuenta el elemento que se agrega), en el cual al interno del array se le asigna un enlace al nuevo array creado obtenido copiando los elementos del array original:

Arrays.copyOf(elementData, newCapacity(minCapacity))

Como segundo parámetro del método, copyOfindicamos el resultado del método newCapacity(int minCapacity), dentro del cual se calcula el nuevo tamaño de la matriz. Se calcula utilizando la siguiente fórmula: int newCapacity = oldCapacity + (oldCapacity >> 1) Para una matriz con el tamaño predeterminado, se cumplirá lo siguiente: >> 1– desplazamiento bit a bit hacia la derecha en uno (un operador que reduce un número a la mitad). Básicamente, significa dividir por 2 elevado a 1. Resulta que dividimos 10 entre 2 y sumamos 10. En total, la nueva capacidad de la matriz es 15, pero como estamos sumando el elemento 11, entonces 15 + 1 = 16. Regresemos a nuestra lista y supongamos que ya le hemos agregado 10 elementos e intentamos agregar 11. La verificación mostrará que no hay espacio en la matriz. En consecuencia, se crea y se llama una nueva matriz Arrays.copyOf, que utiliza internamente el método del sistema System.arraycopy(). O aquí hay un ejemplo claro de un artículo sobre JavaRush: después de todas estas comprobaciones y de aumentar el tamaño de la matriz si es necesario, en un método privado add()se agrega un nuevo elemento al final de la matriz y el parámetro actual sizese incrementa en uno. . Posteriormente, el recolector de basura procesará la matriz anterior. Así es como funciona una matriz dinámica: cuando agregamos elementos, comprobamos si todavía hay espacio en ella. Si hay espacio, simplemente agregamos el elemento al final de la matriz. El final no significa la última celda de la matriz, sino la celda que corresponde al valor size. Agregamos el primer elemento a la matriz; se coloca en la celda con índice [0]. El valor del campo sizeha aumentado en uno y = 1. Agregamos el siguiente elemento: vemos que size = 1, en consecuencia colocamos el elemento en la celda con índice [1] y así sucesivamente. Existe una versión sobrecargada del método con dos parámetros:

public void add(int index, E element)

Podemos especificar la posición (índice) de la celda donde queremos agregar el elemento. Primero, se verifica la exactitud del valor del índice especificado, ya que existe la posibilidad de que se especifique un índice incorrecto, que apuntará a una celda donde no hay nada o que simplemente no existe. Comprobación de índices: index > size || index < 0– si el índice especificado es mayor que el tamaño actual de la matriz o es menor que 0, se lanza una excepción IndexOutOfBoundsException. Luego, si es necesario, se aumenta el tamaño de la matriz, similar al ejemplo anterior. Probablemente hayas escuchado que durante las operaciones de agregar o quitar en una matriz, algo se desplaza a algún lugar (ya sea hacia la derecha o hacia la izquierda). Entonces, el desplazamiento se realiza copiando la matriz: System.arraycopy(elementData, index, elementData, index + 1, s - index); todos los elementos ubicados a la derecha del índice especificado se desplazarán una posición hacia la derecha (índice+1). Y solo después de eso se agrega un nuevo elemento a la matriz interna en el índice especificado. Dado que hemos desplazado parte de la matriz uno hacia la derecha (no se crea una nueva matriz), la celda que necesitamos quedará libre para escribir. El enlace a la matriz anterior se borra y, en el futuro, el recolector de basura se hará cargo de él. Pegue "maserati" en la celda [3], que ya está ocupada: Así, cuando se inserta un elemento en el índice y no hay espacios libres en la matriz, la llamada System.arraycopy()se realizará dos veces: la primera en grow()y la segunda en el método mismo add(index, value), lo que claramente afectará la velocidad de toda la operación de suma. Como resultado, cuando es necesario escribir otro elemento en la matriz interna, pero no hay espacio allí, esto es lo que sucede dentro de ArrayList:

• Se crea una nueva matriz con un tamaño 1,5 veces mayor que la original, más un elemento.
• Todos los elementos de la matriz anterior se copian a la nueva matriz.
• La nueva matriz se almacena en la variable interna del objeto ArrayList y la matriz anterior se declara basura.

La capacidad de los objetos del tipo ArrayList se puede aumentar manualmente utilizando el método:

public void ensureCapacity(int minCapacity)

Al aumentar la capacidad de la matriz por adelantado, puede evitar una redistribución adicional de RAM más adelante. El método aumenta el tamaño de la matriz interna para acomodar la cantidad de elementos pasados minCapacity. El método ensureCapacity()no afecta el campo size, afecta el capacity(tamaño de) la matriz interna. Una vez más recalco que sizeambas son capacitycosas diferentes y ¡es muy importante no confundirlas! Si desea reducir el tamaño de la matriz subyacente a partir de la cual se construye ArrayList al número actual de elementos realmente almacenados, debe llamar a trimToSize(). Después de eliminar elementos de la colección, size()se mostrará la cantidad de elementos realmente existentes y capacityno disminuirá. Supongamos: ingresamos 100 elementos, eliminamos los primeros 50, sizeserá igual a 50, por lo que capacityseguirá siendo 100. Para reducir y capacity, necesitamos usar el método trimToSize(), que ajusta toda nuestra capacidad al tamaño actual. ¿Cómo encaja? Copia nuestra matriz para que no queden celdas vacías (la longitud de la nueva matriz es simplemente igual al tamaño del campo). También puedes agregar elementos a nuestra colección usando el archivo addAll.

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

La primera opción le permite agregar todos los elementos de la colección especificada en el parámetro del método (por ejemplo, otra hoja) a la colección original (insertar al final) para la cual se realizó la llamada al método. La colección pasada (también puede ser un conjunto) se convierte en una matriz usando el archivo toArray(). Naturalmente, la operación de suma también se realiza mediante copia. El segundo es agregar todos los elementos collectiona la lista, comenzando desde el índice index. En este caso, todos los elementos se desplazarán hacia la derecha según el número de elementos de la lista collection. Eliminación de elementos Primero, veamos las opciones clásicas para eliminar elementos de una ArrayList.

public E remove(int index)

Realiza la eliminación por índice y desplaza todos los elementos posteriores (después del elemento en el índice especificado) hacia la izquierda, cerrando así los "agujeros". También devuelve el elemento eliminado (E), que previamente se escribe en una variable adicional antes de la eliminación, cuyo valor obtenemos como resultado de la llamada al método. Para comprender qué es E, deberá familiarizarse con los llamados tipos genéricos. La notación E indica que el método devuelve el tipo de datos que se especificó al crear el objeto ArrayList (recuerde: List <String> list, en consecuencia, en este caso, E será "sustituido" String). Para una comprensión general, le recomiendo encarecidamente que se familiarice con los tipos genéricos. Se verifica la exactitud del índice ingresado y luego, dentro del método, el elemento no se elimina por completo, sino que se llama a un método privado fastRemove(Object[] es, int i)en el que la eliminación ya se produce. Pasamos nuestra matriz y el índice especificado al método como entrada. Los elementos se copian usando System.arraycopy(), se reduce el tamaño de la matriz y luego asignamos nulo al último elemento. Vale la pena señalar que no se crea una nueva matriz: System.arraycopy(es, i + 1, es, i, size - 1 - i); la parte que está a la derecha de la posición bajo el índice especificado (i+1) se copia en nuestra matriz original y se ubica a partir de la misma posición. (i) dónde se encontraba el elemento a eliminar. Por lo tanto, realizamos un desplazamiento hacia la izquierda y borramos nuestro elemento. Intentemos eliminar el elemento en el índice 3 de la siguiente matriz: Consideremos la segunda versión del método:

public boolean remove(Object o)

El método elimina el elemento pasado de la lista o, o más precisamente, el objeto en el enlace especificado. Si un elemento está presente en la lista, se elimina y todos los elementos se desplazan hacia la izquierda. Si el elemento existe en la lista y se elimina correctamente, el método devuelve verdadero; en caso contrario, falso. Similar a la opción de eliminación por índice, el método se llama fastRemove(), donde ocurren exactamente las mismas acciones. La diferencia es que el método remove(Object o)busca adicionalmente el objeto deseado mediante un método equals()de la clase Object. Al eliminar por valor, el bucle recorre todos los elementos de la lista hasta que se encuentra una coincidencia. Sólo se eliminará el primer elemento encontrado. Resumamos: al eliminar elementos de una matriz dinámica, no quedan huecos como en una matriz normal (la celda eliminada no estará vacía). Todos los elementos siguientes (que estaban a la derecha del índice) se desplazan una posición hacia la izquierda. Existen varios métodos adicionales que se pueden utilizar para eliminar elementos de la lista en distintos grados. Veámoslos brevemente. Limpiando nuestra colección:

public void clear()

Un bucle simple forrecorre en iteración todos los elementos de una matriz, asignando nulo a cada elemento. Puedes eliminar aquellos elementos de nuestra colección que estén contenidos en otra colección transferida de esta manera:

public boolean removeAll(Collection< ?> c)

Si necesita eliminar varios elementos, probablemente no debería hacerlo en un bucle condicional: es más conveniente y seguro utilizar el método removeAll(). Acepta una colección de elementos que serán eliminados de la lista. La colección debe contener elementos del mismo tipo que almacena la lista de objetivos. De lo contrario será desechado ClassCastException. El método devolverá verdadero si la lista se cambió como resultado de la llamada al método. Elimina elementos que no pertenecen a la colección pasada:

public boolean retainAll(Collection< ?> c)

Digamos que tenemos una colección:

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

Y el segundo:

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

Luego después listSecond.retainAll(listFirst)quedará listSecond:

"White"
"Red"

Dado que se eliminó "Verde", que no está en listFirst. Pero después listSecond.removeAll(listFirst)quedará listSecond:

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

No pertenecer a la colección pasada: significa que si hay elementos que no están en la colección pasada, entonces es necesario eliminarlos de la primera (a la que se aplica el método). Perteneciente a la colección transferida: en consecuencia, si hay un elemento tanto en la primera como en la segunda colección (transferida), el duplicado de la primera se destruye.

protected void removeRange(int fromIndex, int toIndex)

Elimina de la lista todos los elementos que se encuentran entre el índice especificado inicial (incluido) y el índice especificado final (no incluido). Vale la pena señalar que el método no se puede llamar directamente en un objeto ArrayList. Para usarlo necesitas heredar de AbstractList/ArrayList. El método también es utilizado por otro método (subList, que se analizará más adelante).

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

Elimina elementos de una colección según un predicado determinado. El predicado en sí es una determinada función/algoritmo/condición sobre cuya base se eliminarán uno o más elementos correspondientes a una condición determinada. Predicate— una interfaz funcional (contiene solo un método, por lo que se puede usar como lambda), funciona según el principio "se recibió un parámetro, se devolvió booleano". Esencialmente, el método anula la implementación de la interfaz Collectione implementa la siguiente "estrategia": recorre los elementos y marca aquellos que coinciden con nuestro Predicate; luego se ejecuta por segunda vez para eliminar (y cambiar) los elementos que se marcaron en la primera iteración. Implementemos una interfaz Predicateque devolverá verdadero si dos objetos son iguales:

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

En otra clase, creemos un ArrayList a partir Stringde un objeto de nuestra clase que implemente Predicate:

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

varc1Escribamos el valor "Blanco" en la variable :

filter.varc1 = "White";

Agreguemos algunas líneas a la 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");

Ejecutemos el método en la lista removeIf, al cual le pasaremos nuestro objeto con la condición:

color_list.removeIf(filter);

Como resultado, todas las filas con el valor "Blanco" se eliminarán de la lista, ya que nuestro "predicado" las compara para determinar su igualdad. Lista final: [Negro, Rojo, Amarillo]. Reemplazo de elementos

public E set(int index, E element)

Reemplaza el elemento en la posición especificada indexcon el pasado element. El índice también debe ser mayor que cero y menor que el índice del último elemento; de lo contrario, se generará una excepción IndexOutOfBoundsException. No se producen copias de la matriz interna. Simplemente, en lugar del elemento en el índice especificado, se inserta un nuevo elemento, es decir sobrescribir el valor.

public void replaceAll(UnaryOperator<e> operator)

Cambia todos los elementos de la colección (posible con una condición). Se usa principalmente en combinación con lambdas o una clase anónima (pero para mayor claridad, en el ejemplo simplemente usaremos una clase que implementa la interfaz) que implementa la interfaz UnaryOperatory define sus métodos. Implementemos la interfaz:

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

En otra clase, creemos un ArrayList a partir Stringde un objeto de nuestra clase que implemente UnaryOperator:

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

varc1Escribamos el valor "Blanco" en la variable :

operator.varc1 = "White";

Agreguemos algunas líneas a la 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");

Ejecutemos un método en la lista replaceAllal que pasaremos nuestro objeto operator:

color_list.replaceAll(operator);

Como resultado, todos los valores de la lista fueron reemplazados por "Blanco": [Blanco, Blanco, Blanco, Blanco, Blanco, Blanco]. Y así es como, por ejemplo, puedes eliminar todos los espacios de las cadenas que están en la colección:

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

Otros métodos: puede convertir la matriz de lista ArrayList en una matriz normal utilizando el método:

public Object[] toArray()

o

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

- aquí el tipo de matriz devuelta se determina en runtime Este método permitirá:

1. acelerar algunas operaciones;
2. pasar una matriz como parámetro a un método que no esté sobrecargado para aceptar la colección directamente;
3. Integrar nuevo código basado en colecciones con código heredado que no reconoce colecciones.

Devuelve un objeto de copia de la matriz:

public Object clone()

Tenga en cuenta que el método clone()devuelve el tipo de objeto, por lo que después de llamarlo deberá realizar la conversión a la clase requerida. La clonación crea un nuevo objeto independiente. Verifique la colección para detectar la presencia de un objeto:

public boolean contains(Object o)

Comprueba la presencia de un objeto en la lista (internamente usando el método igual de la clase Objeto, es decir, compara referencias), devuelve verdadero/falso según el resultado. Además de los bucles habituales, puedes recorrer (acceder a cada elemento, así como realizar alguna acción) una colección usando:

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

Así es como podemos mostrar nuestra lista:

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

Sin usar lambdas necesitas usar una clase anónima y anular el método acceptde interfaz Consumer:

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

Obtener un elemento por su índice:

public E get(int index)

Se utiliza para acceso aleatorio a elementos de la colección. Devuelve el elemento ubicado en la lista en el índice especificado. Si index < 0o es index >=el número máximo de elementos en la lista, se lanzará una excepción IndexOutOfBoundsException. Este es el método básico para recuperar un elemento de una lista, y el tiempo para recuperar un elemento por índice siempre será el mismo, independientemente del tamaño de ArrayList, ya que se accede a una celda de matriz específica. Encontrar índices para objetos específicos:

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

Los métodos devuelven el índice del primer elemento (cuando se encuentra el objeto dado por primera vez) o de la última aparición (cuando se encuentra el objeto dado por última vez) en la lista. Si el elemento no existe en la lista, los métodos devolverán -1. Consulta la colección en busca de elementos:

public boolean isEmpty();

El método devuelve verdadero si la lista está vacía (mira si el campo es igual size 0), en caso contrario, falso. Si la lista contiene solo elementos nulos, el método devolverá falso. En otras palabras, este método también tiene en cuenta los elementos nulos. Descubra la cantidad de elementos en una lista:

public int size();

Devuelve el número de elementos de la lista (valores del campo de tamaño). El número de elementos puede diferir de la capacidad de la lista (capacidad). Obtenga un iterador para una lista:

public Iterator< E> iterator();

Devuelve un iterador para una lista para su uso posterior en un bucle o cualquier otro procesamiento. El iterador implementa un comportamiento rápido ante fallos. Si recorre la colección y nota algunas modificaciones (que no se obtuvieron utilizando los métodos del iterador), inmediatamente genera una excepción ConcurrentModificationException. El iterador tiene algo llamado modification count. Cuando el iterador recorre la colección después de cada next/hasNext/remove, verifica este contador. Si no coincide con lo que el iterador esperaba ver, genera una excepción. No consideraré los iteradores en detalle aquí.

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

Devuelve un iterador de lista para su uso posterior en un bucle o cualquier otro procesamiento. La interfaz ListIteratoramplía la interfaz Iteratorpara el recorrido bidireccional de la lista y la modificación de sus elementos. En la versión sobrecargada, puede pasar el índice desde el cual comenzará el "recorrido". El índice en este caso denota el primer elemento a partir del cual el método comenzará a funcionar next(), y cuando se llama al método, previous()el recorrido comenzará desde el elemento bajo el índice "índice pasado - 1".

public Spliterator <E> spliterator()

Java 8 introduce un nuevo tipo de enlace tardío e iterador a prueba de fallos llamado iterador delimitador. Los iteradores separadores le permiten iterar sobre una secuencia de elementos, pero se utilizan de forma diferente. La característica más importante de la interfaz Spliterator es su capacidad para admitir la iteración paralela de partes individuales de una secuencia de elementos y, por lo tanto, la programación paralela.