An ArrayList is an implementation of a variable-length array of the List interface that provides the ability to add, modify, delete, iterate, and so on. This article through the source code to analyze the implementation of ArrayList, precautions, use scenarios, etc. (JDK version 1.8).

ArrayList has the following characteristics:

  • ArrayListBased on the array, can be automatically expanded; However, capacity expansion is time-consuming, so initialization is performedArrayListIt is best to predict the initial capacity;
  • ArrayListAllow insert innullElements;
  • Because of the implementationSerializableInterface, rewrittenwriteObject 和 readObjectMethod, soArrayListSupport serialization and deserialization;
  • ArrayListNot synchronous;
  • ArrayListtheiterator 和 listIteratorThe iterator returned by the method isfail-fast.

define

First, let’s look at the definition of ArrayList:

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

You can see that ArrayList inherits or implements the following classes or interfaces:

  • AbstractList: inheritedAbstractList.AbstractListprovidesListInterface backbone implementation to minimize implementationListRequired work.
  • List: to achieve theListInterface. All optional list operations are provided.
  • RandomAccess: indicates thatArrayListRandom access is supported.
  • Cloneable: indicates that it can be cloned and overwrittencloneMethods.
  • java.io.Serializable: indicates that the class supports serialization.

Here is the class structure hierarchy of ArrayList:

attribute

The properties of an ArrayList are:

// serialize the ID
private static final long serialVersionUID = 8683452581122892189L;

// The capacity is initialized by default
private static final int DEFAULT_CAPACITY = 10;

// ArrayList returns an empty array if its capacity is 0
private static final Object[] EMPTY_ELEMENTDATA = {};

// The empty array is returned if the default constructor (no arguments constructor) is called
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// An array that stores the current element
transient Object[] elementData; 

// The size of the ArrayList (number of elements contained)
private int size;

// The maximum length allocated to the array
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
Copy the code

In addition, there is a modCount attribute inherited from AbstarctList, which represents the number of changes to the ArrayList collection. In traversing the collection, if modCount are changed, will be thrown ConcurrentModificationExceptioin anomalies.

A constructor

In ArrayList, three constructors are provided:

Default constructor

The default constructor that takes no arguments builds an empty list with an initial capacity of 10.

public ArrayList(a) {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the code

Specify the capacity

This constructor builds an empty ArrayList specifying initialCapacity. If negative initialization capacity is specified, IllegalArgumentException is thrown.

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

Construct an array with the given collection

This method constructs a list of the elements for the specified collection in the order in which the iterator for the collection returns them.

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if((size = elementData.length) ! =0) {
        // Determine whether elementData is of type Object[]
        if(elementData.getClass() ! = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }else {
        // Use an empty array instead
        this.elementData = EMPTY_ELEMENTDATA; }}Copy the code

You first convert the elementData passed in to an array, and then copy the elements into the elementData array using the arrays.copyof method.

Basic method

The main methods of ArrayList are as follows:

Get (int index) method

The get method is used to return elements in the list whose index is index.

public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}
Copy the code

Method first check index, if the index over the length of the array, will throw IndexOutOfBoundsException anomalies.

Then use the elementData method to get the element:

E elementData(int index) {
    return (E) elementData[index];
}
Copy the code

Since the underlying implementation of ArrayList is an array, fetching elements by array subscript, its time complexity is O(1).

The add (E, E) method

The add method is used to add the specified element E to the end of the list.

public boolean add(E e) {
    ensureCapacityInternal(size + 1); 
    elementData[size++] = e;
    return true;
}
Copy the code

As you can see, the first is the ensureCapacityInternal(size + 1) method, which checks the array capacity and expands it if it’s not enough for internal use only.

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

The expansion method grow ensures that at least minCapacity elements can be stored. The implementation is as follows:

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);
}
    
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}
Copy the code

After capacity expansion, the capacity can be calculated as follows:

  • Used for the first capacity expansionnewCapacity = oldCapacity + (oldCapacity >> 1);Formula, increase the capacity by half;
  • If the capacity is still less thanminCapacity, expand the capacity tominCapacity;
  • If the capacity is greater thanMAX_ARRAY_SIZE, expand the capacity toInteger.MAX_VALUE.

Finally, use the arrays.copyof method to copy the elements into the new array.

Add (index, element) method

The add method is used to insert elements at the specified position in the list.

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

This method is first to check the position of the specified index, if cross, will be thrown IndexOutOfBoundsException anomalies. Then use the EnrecapacityInternal method to determine the capacity and expand it.

Then, use the system.arrayCopy () method to move the element one bit back after the index position and assign the index position to Element.

Remove (index) method

The remove method is used to remove elements in a list at the index position.

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

First, use the rangeCheck method to check if the index is out of bounds, and then modify modCount, which increases the number of changes by one. Use the elementData method to get the element at the index position for later return.

Using size-index-1 to calculate the number of bits moved to the left, and using the system.arrayCopy () method to move the element one bit to the left indicates that the element has been deleted. Finally, set the element in position –size to null to prevent the object from drifting and causing the JVM to reclaim it.

The Iterator Iterator

Iterators provide a way to access elements in a collection. The iterator() method in the Array class is used to return an iterator from the container object that points to the beginning of the list.

public Iterator<E> iterator(a) {
    return new Itr();
}
Copy the code

The Itr class is implemented as follows:

private class Itr implements Iterator<E> {
    int cursor;       // The index of the next element to return
    int lastRet = -1; // The index of the last returned element, or -1 if not
    int expectedModCount = modCount;

    Itr() {}

    public boolean hasNext(a) {
        returncursor ! = size; }@SuppressWarnings("unchecked")
    public E next(a) {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    public void remove(a) {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw newConcurrentModificationException(); }}final void checkForComodification(a) {
        if(modCount ! = expectedModCount)throw newConcurrentModificationException(); }...}Copy the code

The main methods of the Itr class are as follows:

  • next(): Gets the next element in the sequence;
  • hasNext(): Checks if there is another element in the sequence;
  • remove(): Removes the last element returned by the iterator.