Source code analysis of ArrayList

Implemented interface

• This article is based on Oracle JDK1.8 Start a discussion
• ArrayList be located java.util It's a bag
• ArrayList Declaration of a class ：

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

• ArrayList Inherited AbstractList, see AbstractList Source code , Realized List Interface

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E>

• and ArrayList Once again List Interface , Don't you think it's superfluous ？ actually , There is a reason for this design ：
• List The interface contains many methods , Realized List The class of the interface needs to replace all the methods , And the specific method implementation of each implementation class is different , such as ArrayList and LinkedList about add The concrete implementation of is certainly different .
• however ArrayList and LinkedList The implementation of some methods is exactly the same , such as size() Method
• Now , If you add one more List Implementation class of , Write some methods with the same method body repeatedly , Cannot reuse code
• At this time, the template method pattern in the design pattern is used , hold List The common methods of the implementation classes are abstracted to AbstractList in , And provide the default implementation , In this way, the lower implementation class inherits AbstractList, Direct inheritance of common methods , You don't have to write some code repeatedly

RandomAccess

• This interface is an empty interface , The aim is to speed up ArrayList The speed of random access

public interface RandomAccess {
    }

Cloneable

• This interface is an empty interface , After implementation, you can rewrite clone Method to implement deep copy

public interface Cloneable {
    }

java.io.Serializable

• This interface is an empty interface , The purpose is to facilitate serialization

public interface Serializable {
    }

Member variables

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

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

    /** *  Create an empty ArrayList when , Assignment use  */
    private static final Object[] EMPTY_ELEMENTDATA = {
    };

    /** *  The default empty array , Use... When initializing  */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {
    };

    /** *  An array of actual data  */
    transient Object[] elementData; // non-private to simplify nested class access

    /** *  The actual number of elements stored in the array  */
    private int size;

Constructors

• There are three constructors
  
• Parameter free constructor

public ArrayList() {
    
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
//elementData  An array for storing data 
transient Object[] elementData;    
// During parameterless initialization , Assign to an empty array 
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {
    };

• Initialize the constructor according to the capacity

public ArrayList(int initialCapacity) {
    
        if (initialCapacity > 0) {
    
            // Generate a based on capacity Object Array 
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
    
            // The parameter is equal to 0  Then assign an empty array 
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
    
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

• According to the existing List Initialize constructor

public ArrayList(Collection<? extends E> c) {
    
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
    
            // If not Object[] type   Then perform the copy operation ,Arrays.copyOf Called at the bottom System.arraycopy()
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
    
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

clone Method

public Object clone() {
    
        try {
    
        	// Call the parent class first clone clone 
            ArrayList<?> v = (ArrayList<?>) super.clone();
            // Bottom or call System.arraycopy();
            v.elementData = Arrays.copyOf(elementData, size);
            // The modification times are set to 0
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
    
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
    }

get Method

public E get(int index) {
    
		// First check index Is it legal 
        rangeCheck(index);

        return elementData(index);
}
/** * Check index Is it legal  */    
private void rangeCheck(int index) {
    
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
    
/** * return index  The element of location  */   
E elementData(int index) {
    
        return (E) elementData[index];
}

set Method

public E set(int index, E element) {
    
		// Check index Is it legal 
        rangeCheck(index);
		// Take out the old elements 
        E oldValue = elementData(index);
        // hold index Replace the element of position with a new element 
        elementData[index] = element;
        return oldValue;
}

add Method ： Capacity expansion will occur here

public boolean add(E e) {
    
		// Determine if the capacity is sufficient   If it's not enough, expand the capacity 
        ensureCapacityInternal(size + 1);
        elementData[size++] = e;
        return true;
}

private void ensureCapacityInternal(int minCapacity) {
    
        // If the array is empty   For the first time add Elements   Take the largest Capacity 
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }
   
private void ensureExplicitCapacity(int minCapacity) {
    
        // Number of changes +1
        modCount++;

        // If needed Capacity  Greater than the present elementData The length of   You need to expand 
        if (minCapacity - elementData.length > 0)
        	// Capacity expansion 
            grow(minCapacity);
}

Expansion mechanism grow(minCapacity);

private void grow(int minCapacity) {
    
        //  Record the old capacity 
        int oldCapacity = elementData.length;
        // New capacity is   Old capacity +  Old capacity 1/2
        // The shift operation is used here   Moving one bit to the right is equivalent to dividing by 2
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // Take a maximum 
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // If the new capacity exceeds Integer.MAX_VALUE - 8  Then put newCapacity The assignment is Integer.MAX_VALUE
        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;
    }

remove Method

public E remove(int index) {
    
        // Check that the subscript is legal 
        rangeCheck(index);

        // Number of changes +1
        modCount++;
        // Save old values 
        E oldValue = elementData(index);

        // After deleting the element   The number of elements the array needs to move 
        int numMoved = size - index - 1;
        if (numMoved > 0)
            // Move array 
            System.arraycopy(elementData, index + 1, elementData, index,
                    numMoved);
        // Set as null  convenient gc
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

clear Method

public void clear() {
    
        // Number of changes +1
        modCount++;

        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

addAll Method

public boolean addAll(int index, Collection<? extends E> c) {
    
        // Check that the subscript is legal 
        rangeCheckForAdd(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        // Determine whether capacity expansion is needed 
        ensureCapacityInternal(size + numNew);  // Increments modCount

        // Calculate the number of elements that need to be moved 
        int numMoved = size - index;
        // The movement here is to index The next element moves back numMoved individual   The purpose is to make room for the elements inserted below 
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                    numMoved);
        // Insert data into index It's about 
        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
}

iterator

public Iterator<E> iterator() {
    
		// Commonly used iterators   It's actually ArrayList An inner class Itr
        return new Itr();
}

• Iterator resolution

private class Itr implements Iterator<E> {
    
        // Cursor pointing to the next element 
        int cursor;       // index of next element to return
        // Last returned element 
        int lastRet = -1; // index of last element returned; -1 if no such
        // Note here ！！！  When getting iterators ,expectedModCount It will only be assigned once 
        //  So when external modCount After change , Internal class expectedModCount It doesn't change 
        int expectedModCount = modCount;

        /** * Determine if there is the next element  */
        public boolean hasNext() {
    
            // Directly determine whether the cursor is ==size
            return cursor != size;
        }

        @SuppressWarnings("unchecked")
        public E next() {
    
            // Determine whether the modified version is consistent 
            checkForComodification();
            int i = cursor;
            // The subscript is greater than size  Throw an exception 
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            // Point to the next element 
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }

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

            try {
    
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                // The modified version will be updated here 
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
    
                throw new ConcurrentModificationException();
            }
        }

        @Override
        @SuppressWarnings("unchecked")
        public void forEachRemaining(Consumer<? super E> consumer) {
    
            Objects.requireNonNull(consumer);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i >= size) {
    
                return;
            }
            final Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length) {
    
                throw new ConcurrentModificationException();
            }
            while (i != size && modCount == expectedModCount) {
    
                consumer.accept((E) elementData[i++]);
            }
            // update once at end of iteration to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }

        // When the internal and external modification times are inconsistent   This will cause concurrent modification exceptions 
        final void checkForComodification() {
    
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

Other methods

	/** *  Get number of elements  */
    public int size() {
    
        return size;
    }

    /** *  Determine whether it is null  */
    public boolean isEmpty() {
    
        return size == 0;
    }
    
    /** *  Determine whether it contains elements o  This is the call indexOf  See if the index of the element is >0 */
    public boolean contains(Object o) {
    
        return indexOf(o) >= 0;
    }
    
    public int indexOf(Object o) {
    
        if (o == null) {
    
            // If the object is empty   Then take the index in the array where the first object is empty 
            for (int i = 0; i < size; i++)
                if (elementData[i] == null)
                    return i;
        } else {
    
            // Not empty   Then iterate over the array   Use equals Judge 
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }