Introduction to the

  1. ArrayList is a common array-based container class that implements the List interface and supports null insertion. In addition to implementing the basic List interface methods, methods are provided to manually manipulate the size of the array internally used to store data.
  2. size.isEmpty.get.set.iteratorAs well aslistIteratorAll the methods are uniformly amortized constant time complexity. All other operations are completed in linear time. ArrayList has a lower time complexity than ArrayListLinkedList.
  3. Each ArrayList instance has onecapacityProperty, which represents the length of the array of internal stored elements. Capacity is greater than or equal to the number of actual stored elements. Capacity automatically resizes each time a new element is added to the ArrayList. This parameter is available if a large amount of data is addedensureCapacityMethod expands Capacity in advance, which reduces the time overhead of frequent array size changes and reassignment operations.
  4. ArrayList is non-thread-safe.

Class variables

private static final int DEFAULT_CAPACITY = 10;
Copy the code
  • The default size of the internal array is 10, but the default size is not created immediately upon instantiation, only the first add operation will create an array of length 10.

Member variables

transient Object[] elementData;
private int size;
Copy the code
  • ElementData is an array that stores data internally
  • Size is the actual number of data stored

The constructor

  • No parameter constructor
/**
   * Constructs an empty list with an initial capacity of ten.
   */
public ArrayList() {
     this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the code
  • Parameter constructor – passes in the initial capacity
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); }}Copy the code

Create a new array of initial capacity if the initial capacity is greater than 0, assign EMPTY_ELEMENTDATA to elementData if it is 0, otherwise throw an exception. * Parameter constructors – pass in collections

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

The constructor

  • Add operation -add(E E)
public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
	
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

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);
    }
Copy the code
  1. If you are adding elements for the first time, create a new array with a default size of 10
  2. If the element is not added for the first time and exceeds the length of the current array, increase to 1.5 times the length
  • Add (int index, E element)
public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
Copy the code

To insert data at the specified index position, first make sure the array length is sufficient, then expand. Then move the full second half of the index one bit to the right, using system. arrayCopy, and finally assign the value at index. The AddAll operation is similar: first, make sure the array is long enough, copy the new array if you append the value directly, and copy the original array once if you interpolate in the middle, and then copy again.

Delete operation -remove(int index)

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;
    }
Copy the code

Arraycopy moves the entire right side of index one bit to the left and assigns the rightmost value to NULL.

  • trimToSize
public void trimToSize() { modCount++; if (size < elementData.length) { elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); }}Copy the code

TrimToSize can be used to remove excess array space. If the array is determined to be unchanged, you can use this method to reduce the amount of memory.

  • ensureCapacity
public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // any size if not default element table
            ? 0
            // larger than default for default empty table. It's already
            // supposed to be at default size.
            : DEFAULT_CAPACITY;

        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }
Copy the code

A method that expands the array in advance. If you know how much to add in advance, you can call this method to preset the size of the array. The preset idea is also to preferentially expand to 1.5 times the current capacity, if not directly use minCapacity. This method can greatly reduce the assignment time in the case of large data volumes.