ArrayList

1. An overview of the

Because ArrayList is implemented based on arrays, it supports fast random access. The RandomAccess interface indicates that this class supports fast RandomAccess.

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

The default size of the array is 10.

private static final int DEFAULT_CAPACITY = 10;
Copy the code

Expansion and 2.

When adding an element, use the ensureCapacityInternal() method to ensure that the capacity is sufficient. If not, use the grow() method to expand the new capacity with oldCapacity + (oldCapacity >> 1), Namely oldCapacity + oldCapacity / 2. OldCapacity >> 1 needs to be rounded, so the new capacity is about 1.5 times the oldCapacity. (if oldCapacity is even, it is 1.5 times; if oldCapacity is odd, it is 1.5 times -0.5)

The expansion operation requires arrays.copyof () to copy the entire array into the new array, which is expensive, so it’s best to specify the approximate size of the ArrayList object when you create it to reduce the number of times of expansion.

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

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(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

3. Delete elements

You need to call system.arrayCopy () to copy all the elements after index+1 to the index position. The time complexity of this operation is O(N). As you can see, ArrayList is very expensive to remove elements.

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

4. The serialization

ArrayList is implemented based on arrays and has a dynamic scaling feature, so not all arrays holding elements will be used, so there is no need to serialize them all.

The array that holds the elements, elementData, is decorated with the keyword transient, which declares that the array will not be serialized by default.

transient Object[] elementData; // non-private to simplify nested class access
Copy the code

ArrayList implements writeObject() and readObject() to control only the elements in the serialized array that populate that part of the content.

private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { elementData = EMPTY_ELEMENTDATA; // Read in size, and any hidden stuff s.defaultReadObject(); // Read in capacity s.readInt(); // ignored if (size > 0) { // be like clone(), allocate array based upon size not capacity ensureCapacityInternal(size); Object[] a = elementData; // Read in all elements in the proper order. for (int i=0; i<size; i++) { a[i] = s.readObject(); }}}Copy the code

private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();

    // Write out size as capacity for behavioural compatibility with clone()
    s.writeInt(size);

    // Write out all elements in the proper order.
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }

    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}
Copy the code

Serialization requires the ObjectOutputStream’s writeObject() to convert the object to a byte stream and output it. The writeObject() method, on the other hand, will reflect the call to the object’s writeObject() when the passed object has a writeObject(). Deserialization uses the readObject() method of ObjectInputStream, and the principle is similar.

ArrayList list = new ArrayList();
ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream(file));
oos.writeObject(list);
Copy the code

5.Fail-Fast

ModCount is used to record the number of times the ArrayList structure has changed. A structure change is any operation that adds or removes at least one element, or resizing an internal array. Just setting the value of an element does not count as a structure change.

When serializing or iterative operations such as, need to compare the difference between before and after the operation modCount whether to change, if change the need to throw ConcurrentModificationException. Refer to the writeObject() method in the serialization section above.