Funcionamiento interno de ArrayList en Java

Posted on by Rudeus Greyrat

ArrayList es una implementación de array de tamaño variable en Java. ArrayList crece dinámicamente y garantiza que siempre haya un espacio para agregar elementos. La estructura de datos de respaldo de ArrayList es una array de clases de objetos. La clase ArrayList en Java tiene 3 constructores. Tiene su propia versión de los métodos readObject y writeObject. La array de objetos en ArrayList es transitoria . Implementa RandomAccess, Cloneable y java.io.Serializable (que son Marker Interface en Java )

Sintaxis:

public class ArrayList<E> 
extends AbstractList<E> 
implements List<E>, RandomAccess, Cloneable, java.io.Serializable

Internamente, una ArrayList usa una array Object[] que es una array de objetos. Todas las operaciones como eliminar, agregar y actualizar los elementos ocurren en esta array Object[].

/**
    * The array buffer into which the elements of the ArrayList are stored.
    * The capacity of the ArrayList is the length of this array buffer. Any
    * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
    * will be expanded to DEFAULT_CAPACITY when the first element is added.
    */
transient Object[] elementData; // non-private to simplify nested class access

El código anterior es de Java 8 en Java 7, la array se declara como un objeto transitorio privado, pero en Java 8 no es privado porque no es privado para simplificar el acceso a una clase anidada como Itr, ListItr, SubList.

Inicialización

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

mientras se declara ArrayList a continuación, el código se ejecuta cuando se invoca el constructor predeterminado de la clase ArrayList.

En Java 7

public ArrayList() {
     this(10);
}

Por la presente, la capacidad predeterminada del tamaño de la array es 10.

En Java 8

private static final int DEFAULT_CAPACITY = 10;\\ Default initial capacity.
  
// Shared empty array instance used for empty instances.
private static final Object[] EMPTY_ELEMENTDATA = {};

  /**
   * Shared empty array instance used for default sized empty instances. We
   * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
   * first element is added.
   */
   
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

Aquí, la Lista se inicializa con una capacidad predeterminada de 10. La Lista de arreglos con datos de elementos == DEFAULTCAPACITY_EMPTY_ELEMENTDATA se expandirá a DEFAULT_CAPACITY cuando se inserte el primer elemento en la lista de arreglos (agregando el primer elemento a ArrayList).

Constructores     

Para crear una ArrayList, primero debe crear un objeto de la clase ArrayList. ArrayList contiene 3 tipos de constructores en Java 8  

  1. ArrayList() : este constructor es para inicializar una lista vacía.
  2. ArrayList (capacidad int): en este constructor, podemos pasar la capacidad como un parámetro, utilizado para inicializar la capacidad por parte del usuario.
  3. ArrayList(Collection c): En este constructor, podemos pasar una Collection c como parámetro, en la que una lista Array contendrá los elementos de la Collection c.

ArrayList(): este constructor se usa para crear un ArrayList vacío con una capacidad inicial de 10 y es un constructor predeterminado. Podemos crear una lista de arrays vacía por el nombre de referencia arr_name objeto de la clase ArrayList como se muestra a continuación.

ArrayList arr_name = new ArrayList();

A continuación se muestra el código interno de este constructor (en Java 8):     

// Constructs an empty Arraylist with an initial capacity of ten.
    
public ArrayList() {
     this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

En el código anterior, DEFAULTCAPACITY_EMPTY_ELEMENTDATA se cambiará a DEFAULT_CAPACITY cuando agreguemos el primer elemento a la lista de arreglos. (CAPACIDAD_DEFAULT =10).

ArrayList(int capacidad): Este constructor se utiliza para crear un ArrayList con la capacidad inicial dada por el usuario. Si queremos crear una ArrayList con un tamaño específico, podemos pasar el valor a través de este constructor. Internamente se crea una array de objetos con el tamaño dado por el usuario. Por ejemplo, si un usuario quiere que el tamaño de la lista Array sea 7, entonces el valor 7 se puede pasar en el constructor, se puede crear como se muestra aquí:

ArrayList arr = new ArrayList(7);

A continuación se muestra el código interno de este constructor (en Java 8):   

public ArrayList(int initialCapacity) {

       if (initialCapacity > 0) {
           this.elementData = new Object[initialCapacity];  
           
       } else if (initialCapacity == 0) {
       
           this.elementData = EMPTY_ELEMENTDATA;
       } else {
       
           throw new IllegalArgumentException("Illegal Capacity: "+  initialCapacity);
       }
}

En el código anterior, el tamaño que se puede pasar al constructor es mayor que 0 ( initialCapacity>0 ), la array de objetos creados tendrá la capacidad dada. Si la capacidad pasada es igual a 0 ( initialCapacity == 0 ), se creará una Arraylist vacía. Si la capacidad inicial es inferior a 0 ( initialCapacity<0 ), se  generará  IllegalArgumentException .

ArrayList(Collection<? extends E> c ): este constructor se usa para crear una lista de arreglos inicializada con los elementos de la colección pasados ​​al constructor (Collection c ). El objeto de ArrayList se puede crear sobre la colección específica pasada al constructor.

ArrayList<String> arrayList = new ArrayList<String>(new LinkedList());

  A continuación se muestra el código interno de este constructor (en Java 8):  

public ArrayList(Collection<? extends E> c) {
       elementData = c.toArray();
       if ((size = elementData.length) != 0) {
       
           // c.toArray might (incorrectly) not return Object[] 
           if (elementData.getClass() != Object[].class)
               elementData = Arrays.copyOf(elementData, size, Object[].class);
       } else {
       
           // replace with empty array.
           this.elementData = EMPTY_ELEMENTDATA; 
       }
   }

Los elementos de la colección deben colocarse en la lista Array. Este código verificará el tamaño de la colección pasada. Si el tamaño es mayor que cero, se usa el método Arrays.copyOf() para copiar la colección en la array. Se lanza NullPointerException si la colección que pasó al constructor es nula. 

Ejemplo:

Java

import java.util.ArrayList;
import java.util.Collection;
 
public class Main {
    public static void main(String args[])
    {
        Collection<Integer> arr = new ArrayList<Integer>();
        arr.add(1);
        arr.add(2);
        arr.add(3);
        arr.add(4);
        arr.add(5);
        System.out.println("This is arr " + arr);
        ArrayList<Integer> newList
            = new ArrayList<Integer>(arr);
        System.out.println("This is newList " + newList);
        newList.add(7);
        newList.add(700);
        System.out.println(
            "This is newList after adding elements "
            + newList);
    }
}
Producción

This is arr [1, 2, 3, 4, 5]
This is newList [1, 2, 3, 4, 5]
This is newList after adding elements [1, 2, 3, 4, 5, 7, 700]

Aquí los elementos en el arr se pasan a newList . Entonces, los elementos de arr se copiaron en newList, esto se muestra en el ejemplo anterior.

¿Cómo crece dinámicamente el tamaño de ArrayList? [método agregar()]

Profundicemos en cómo agregar un método que funcione en la lista Array con la ayuda del código interno de Java 8 de ArrayList . Si intentamos agregar un elemento usando el método add() en la lista de arreglos Internamente, entonces verifica la capacidad para almacenar el nuevo elemento o no. De lo contrario, la nueva capacidad se calcula como se muestra en el código interno de add( ) método.

public boolean add(E e) {
       ensureCapacityInternal(size + 1);  // Size Increments
       elementData[size++] = e;
       return true;
}

 Aquí, en el método add(Object), se pasa el objeto y se aumenta el tamaño. La capacidad interna de la array está garantizada por el método sureCapacityInternal() 

private void ensureCapacityInternal(int minCapacity) {

       if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
           minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
       }
       ensureExplicitCapacity(minCapacity);
}

Este método sureExplicitCapacity determina cuál es el tamaño actual de los elementos y cuál es el tamaño máximo de la array. aquí La capacidad mínima será el máximo de la capacidad predeterminada y mincapacity luego se utiliza como argumento para el método de asegurarExplicitCapacity mincapacity.

private void ensureExplicitCapacity(int minCapacity) {
       modCount++;
       
       // overflow-conscious code
       if (minCapacity - elementData.length > 0)
           grow(minCapacity);
}

Aquí, si (mincapacity – arraylength) es mayor que 0(>0), entonces el tamaño de la array crecerá llamando al método grow() y mincapacity a medida que pasa el argumento.

/**
    * Increases the capacity to ensure that it can hold at least the
    * number of elements specified by the minimum capacity argument.
    *
    * @param minCapacity the desired minimum capacity
    */
   private void grow(int minCapacity) {
       // overflow-conscious code
       int oldCapacity = elementData.length;
       int newCapacity = oldCapacity + (oldCapacity >> 1);
       if (newCapacity - minCapacity < 0)
           newCapacity = minCapacity;
       if (newCapacity - MAX_ARRAY_SIZE > 0)
           newCapacity = hugeCapacity(minCapacity);
       // minCapacity is usually close to size, so this is a win:
       elementData = Arrays.copyOf(elementData, newCapacity);
}

El método de crecimiento en la clase ArrayList proporciona la nueva array de tamaño. En Java 8 y versiones posteriores, se calcula la nueva capacidad, que es un 50 % más que la capacidad anterior, y la array aumenta en esa capacidad. Utiliza Arrays.copyOf, que aumenta la array a la nueva longitud mediante el operador de desplazamiento a la derecha y también crecerá en un 50% de la capacidad anterior.

int newCapacity = oldCapacity + (oldCapacity >> 1);

Por ejemplo, si el tamaño de la array es 10 y ya todas las habitaciones estaban ocupadas por los elementos, mientras agregamos un nuevo elemento ahora, la capacidad de la array se incrementará a 10+ (10>>1) => 10+ 5 => 15. Aquí el tamaño se incrementa de 10 a 15. Para aumentar el tamaño en un 50% usamos el operador de desplazamiento a la derecha. Mientras que en Java 6 es totalmente diferente del cálculo anterior al aumentar el tamaño de la array, en Java 6 la capacidad aumenta en la cantidad de 1.5X

int newCapacity = (oldCapacity * 3)/2 + 1;

¿Cómo funciona el método remove en ArrayList? [ArrayList se reduce automáticamente ]

Para eliminar un elemento de ArrayList en Java, podemos usar remove(int i) [0 index based] o remove(Object o) . al eliminar cualquier elemento de una ArrayList, internamente todos los elementos subsiguientes deben desplazarse a la izquierda para llenar el espacio creado por el elemento eliminado en la array y luego restar uno de sus índices. el tamaño de la array se reducirá en 1 ( — tamaño ).

// Removes the element at the specified position in this list.
// Shifts any subsequent elements to the left (subtracts one from their indices).
public E remove(int index) {
 rangeCheck(index);
 modCount++;
 E oldValue = elementData(index);
 int numMoved = size - index - 1;
 if (numMoved > 0)
   System.arraycopy(elementData, index+1, elementData, index, numMoved);
 elementData[--size] = null; // clear to let GC do its work
 return oldValue;
}

El método System.arrayCopy se utiliza para este propósito. Aquí index+1 es la posición inicial e index es la posición final. Dado que el elemento en el índice de posición se elimina, los elementos que comienzan en el índice + 1 se copian en el destino a partir del índice. 

System.arraycopy(elementData, index+1, elementData, index, numMoved);

Así es como ArrayList se reduce automáticamente.

Mejores prácticas en la creación de ArrayList

Cada vez que creamos un ArrayList y alcanza su umbral, internamente crea un nuevo objeto ArrayList con una nueva capacidad y copia todos los elementos antiguos del antiguo ArrayList a un nuevo objeto. Este proceso tomará más espacio y tiempo, incluso proporciona flexibilidad para hacerlo.

Límite

Threshold = (Current Capacity) * (Load Factor)

El factor de carga es la medida que decide cuándo aumentar la capacidad de ArrayList. El factor de carga predeterminado de un ArrayList es 0.75f. Por ejemplo, la capacidad actual es 10. Por lo tanto, el factor de carga = 10*0,75=7 mientras se agrega el tamaño de la array del séptimo elemento aumentará. Por lo tanto, sería una buena práctica si elegimos la capacidad inicial, teniendo en cuenta la cantidad de elementos esperados como aprox.

Rendimiento de ArrayList       

La complejidad temporal de las operaciones comunes en ArrayList java.

  • add(): para agregar un solo elemento O (1) . Agregar n elemento en la lista de arreglos toma O(n).
  • add ( índice, elemento ): agregar elemento en un índice particular en ejecuciones promedio en tiempo O (n).
  • get(): es siempre una operación O(1) de tiempo constante.
  • remove(): se ejecuta en tiempo lineal O(n). Tenemos que iterar toda la array para encontrar el elemento adecuado para su eliminación.
  • indexOf():  se ejecuta en toda la array e itera a través de todos y cada uno de los elementos. El peor de los casos será el tamaño de la array n. Por lo tanto, requiere tiempo O (n).
  • contiene(): la implementación se basa en indexOf(). Entonces también se ejecutará en tiempo O(n).
  • Las operaciones size , isEmpty , set , iterator y listIterator se ejecutan en tiempo constante O(1)

Nota:

  • ArrayList es una implementación de array de tamaño variable en Java.
  • La estructura de datos de respaldo de ArrayList es una array de la clase Object.
  • Al crear una ArrayList, puede proporcionar la capacidad inicial y luego la array se declara con la capacidad dada.
  • El valor de capacidad predeterminado es 10. Si el usuario no especifica la capacidad inicial, se utiliza la capacidad predeterminada para crear una array de objetos.
  • Cuando se agrega un elemento a una ArrayList, primero verifica si el nuevo elemento tiene espacio para llenar o si necesita aumentar el tamaño de la array interna. Si se debe aumentar la capacidad, se calcula la nueva capacidad, que es un 50% más que el la capacidad anterior y la array aumenta en esa capacidad.

Publicación traducida automáticamente

Artículo escrito por jagadeepmahendran y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *