A deep understanding of ArrayList source code, interview essential!

“This is my fourth day of participating in the First Challenge 2022. For more details: First Challenge 2022.”

preface

An ArrayList is a List implemented as an array. Compared with an array, it has the ability to expand dynamically, so it can also be called a dynamic array.

An ArrayList can store any type of data, and it’s a sequential container that stores the data in the same order that we put it in, and it allows us to put null elements in.

Inheritance system

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

• ArrayList implements lists, providing basic add, delete, traverse, and so on.

• ArrayList implements RandomAccess and provides RandomAccess.

• ArrayList implements Cloneable and can be cloned.

• ArrayList implements Serializable and can be serialized.

The source code parsing

attribute

/** * Default capacity */
private static final int DEFAULT_CAPACITY = 10;

/** * an empty array. */ is used if the passed capacity is 0
private static final Object[] EMPTY_ELEMENTDATA = {};

/** * an empty array, which is used when passing in the capacity. The first element is reinitialized to the default size */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/** * an array of elements */
transient Object[] elementData; // non-private to simplify nested class access

/** * The number of elements in the set */
private int size;
Copy the code

(1) DEFAULT_CAPACITY: The default capacity is 10, which is the default capacity when created using new ArrayList().

(2) EMPTY_ELEMENTDATA: an empty array, which is created with new ArrayList(0).

(3) DEFAULTCAPACITY_EMPTY_ELEMENTDATA: This is an empty array created with new ArrayList(), which differs from EMPTY_ELEMENTDATA in that using this empty array when adding the first element will initialize DEFAULT_CAPACITY (10).

(4) elementData: Where the elements are actually stored.

(5) Size: the actual number of stored elements, not the length of the elementData array.

Why is the elementData array of an ArrayList decorated with transient?

Due to the automatic expansion mechanism of ArrayList, the size of the elementData array of ArrayList is often larger than the number of existing elements. If the array is serialized without transient, the free positions in the array will be serialized, wasting a lot of space.

The corresponding writeObject and readObject methods of serialization and deserialization are rewritten in ArrayList. When iterating over a group of elements, size is used as the end flag to serialize only the elements already in ArrayList.

ArrayList(int initialCapacity) constructor

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        // If the initial capacity passed in is greater than 0, a new array is created to store the elements
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        // If the initial capacity passed in is equal to 0, use the empty array EMPTY_ELEMENTDATA
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        // If the initial capacity passed in is less than 0, an exception is thrown
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}Copy the code

ArrayList() constructor

public ArrayList(a) {
    // If no initial capacity is passed in, the empty array DEFAULTCAPACITY_EMPTY_ELEMENTDATA is used
    // This array is expanded to the default size of 10 when the first element is added
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the code

ArrayList constructor

/** * initializes the elements of the passed collection into the ArrayList */
public ArrayList(Collection<? extends E> c) {
    // Set to array
    elementData = c.toArray();
    if((size = elementData.length) ! =0) {
        // Check whether c. toarray () returns an Object[]. If not, copy it back to Object[]. Class
        if(elementData.getClass() ! = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }else {
        // If c is an empty collection, initialize to an empty array EMPTY_ELEMENTDATA
        this.elementData = EMPTY_ELEMENTDATA; }}Copy the code

The add (E, E) method

The average time to add elements to the end is O(1).

public boolean add(E e) {
    // Check whether the capacity needs to be expanded
    ensureCapacityInternal(size + 1);
    // Insert the element to the last digit
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // If the array DEFAULTCAPACITY_EMPTY_ELEMENTDATA is empty, initialize to default size 10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

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

    if (minCapacity - elementData.length > 0)
        / / capacity
        grow(minCapacity);
}

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // The new capacity is 1.5 times the old capacity
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // If the new capacity is found to be smaller than the required capacity, the required capacity prevails
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // If the new capacity exceeds the maximum capacity, use the maximum capacity
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // Copy a new array with the new capacity
    elementData = Arrays.copyOf(elementData, newCapacity);
}
Copy the code

Add (int index, E Element) method

Adding elements to a specified location takes O(n) on average.

public void add(int index, E element) {
    // Check for overbounds
    rangeCheckForAdd(index);
    // Check whether the capacity needs to be expanded
    ensureCapacityInternal(size + 1);
    // Move inex and the element after it one bit back to leave the index position empty
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // Insert the element at the index position
    elementData[index] = element;
    // The size increases by 1
    size++;
}

private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
Copy the code

Why is ArrayList slow to add?

We can see that the ArrayList has index additions as well as index additions, before which it has a step to check the length ensureCapacityInternal, which means that if the length is insufficient, it needs to be expanded.

At the time of expansion, there was a difference between older JDK versions and later versions, which became more efficient by moving the bit to the right, essentially dividing by 2. int newCapacity = oldCapacity + (oldCapacity >> 1); The size of the new array is 1.5 times that of the old one.

Arraycopy (elementData, index, elementData, index + 1, size-index); arrayCopy (elementData, index, index + 1, size-index); To better explain, here is a picture, as follows:

Let’s say I have an array like this and I need to add an element a at index 4

As you can see from the code, it copies an array, starting at index 4, and then puts it at index 4+1

We’ve made room for the element we want to add, and we’ve done that by putting element A in the index position.

This is just a small List, if I go to a List of hundreds of thousands of size to add an element, then I have to copy all the following elements, and then it’s even slower if it involves scaling things up.

AddAll method

Find the union of two sets.

/** * Adds all the elements in collection C to the current ArrayList */
public boolean addAll(Collection<? extends E> c) {
    // Convert collection C to an array
    Object[] a = c.toArray();
    int numNew = a.length;
    // Check whether the capacity needs to be expanded
    ensureCapacityInternal(size + numNew);
    // Copy all elements in c to the end of the array
    System.arraycopy(a, 0, elementData, size, numNew);
    // size increases the size of c
    size += numNew;
    // Return true if c is not empty, false otherwise
    returnnumNew ! =0;
}
Copy the code

Get (int index) method

Gets the element at the specified index position in O(1) time.

public E get(int index) {
    // Check for overbounds
    rangeCheck(index);
    // Return the element in the array index position
    return elementData(index);
}

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

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

(1) check whether the index is crossing the line, here only to check whether the upper bound, if the upper throw IndexOutOfBoundsException abnormalities, if the lower bound is an ArrayIndexOutOfBoundsException anomalies.

(2) return the element at index position;

Remove (int index) method

Removes the element at the specified index position in O(n) time.

public E remove(int index) {
    // Check for overbounds
    rangeCheck(index);

    modCount++;
    // Get the element at index position
    E oldValue = elementData(index);

    // If index is not the last digit, move the element after index one digit forward
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);

    // Remove the last element to help the GC
    elementData[--size] = null; // clear to let GC do its work

    // Return the old value
    return oldValue;
}
Copy the code

Remove (Object o) method

Removes the element with the specified element value in O(n) time.

public boolean remove(Object o) {
    if (o == null) {
        // Walk through the array, find the first occurrence of the element, and quickly delete it
        for (int index = 0; index < size; index++)
            // If the element to be deleted is NULL, null is used for comparison, using ==
            if (elementData[index] == null) {
                fastRemove(index);
                return true; }}else {
        // Walk through the array, find the first occurrence of the element, and quickly delete it
        for (int index = 0; index < size; index++)
            // If the elements to be deleted are not null, compare them using equals()
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true; }}return false;
}

private void fastRemove(int index) {
    // There is one less out-of-bounds check
    modCount++;
    // If index is not the last digit, move the element after index one digit forward
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    // Remove the last element to help the GC
    elementData[--size] = null; // clear to let GC do its work
}
Copy the code

(1) Find the first element equal to the specified element value;

(2) Fast delete, fastRemove(int index) relative to remove(int index) less check index out of bounds operation.

RetainAll method

Find the intersection of two sets.

public boolean retainAll(Collection
        c) {
    // Set C cannot be null
    Objects.requireNonNull(c);
    // Invoke the bulk delete method, where complement is passed true to delete elements not included in c
    return batchRemove(c, true);
}

/** * Delete elements from c */
private boolean batchRemove(Collection<? > c,boolean complement) {
    final Object[] elementData = this.elementData;
    // Use read and write to iterate over the array simultaneously
    // The read pointer increments by 1 each time the write pointer is placed in an element
    // No extra space is required, just work on the existing array
    int r = 0, w = 0;
    boolean modified = false;
    try {
        // Traverse the array. If c contains the element, put it in the same position as the pointer.
        for (; r < size; r++)
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // Normally r is equal to size unless c. containes () throws an exception
        if(r ! = size) {// If c. taines () throws an exception, copy the unread elements to the write pointer
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if(w ! = size) {// Set the element after the write pointer to null to help GC
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            // The new size is equal to the position of the write pointer.
            size = w;
            modified = true; }}// Returns true with modifications
    return modified;
}
Copy the code

(1) Traverse the elementData array;

(2) If the element is in C, add the element to the w position of the elementData array and move the W position one bit further;

(3) After traversal, elements before W are common to both, and elements after W (including) are not common to both;

(4) Set the element after w to null to facilitate GC collection;

removeAll

Find the unidirectional difference set of two sets, reserving only the elements in the current set that are not in C, and not the elements in C that are not in the current group.

public boolean removeAll(Collection
        c) {
    // Set c cannot be empty
    Objects.requireNonNull(c);
    // Call the batch delete method, here passing false to complement the element contained in c
    return batchRemove(c, false);
}
Copy the code

And retainAll (Collection
c) the method is similar, except that elements that are not in C are preserved.

conclusion

(1) ArrayList uses arrays to store elements internally. During expansion, half of the space is added each time, and the ArrayList does not shrink.

(2) ArrayList supports random access. Accessing elements through indexes is extremely fast and the time complexity is O(1).

(3) ArrayList adds elements to the tail extremely fast, with an average time complexity of O(1).

(4) ArrayList is slow to add elements to the middle because the average time complexity of moving elements is O(n).

(5) ArrayList removes elements from the tail very quickly, with time complexity O(1).

(6) ArrayList is slow to remove elements from the middle, because the average time complexity of moving elements is O(n).

(7) ArrayList supports union, call addAll(Collection
c).

(8) ArrayList support intersection, call retainAll(Collection
c).

(7) ArrayList support one-way difference set, call removeAll(Collection
c).