JAVA collection: ArrayList source code analysis

ArrayList

List is an important part of Java collections, and ArrayList is the most commonly used list, so it’s worth learning the source code. (The following code comes from JDk1.8.0_20)

Inheritance structure

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

ArrayList can be accessed randomly from AbstractList, Cloneable, Java.io.Serializable interface. Because ArrayList is an array implementation at the bottom.

Member variables

The default initial capacity is 10

private static final int DEFAULT_CAPACITY = 10;

An empty array, used when the initialization parameter is 0

private static final Object[] EMPTY_ELEMENTDATA = {};

An empty array, used when initialized by default, differs from EMPTY_ELEMENTDATA in that it is expanded to a different size the first time an element is added

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

An array that stores elements

transient Object[] elementData;

The constructor

ArrayList has three constructors, including a no-argument constructor that takes an int and a collection constructor.

When the argument is 0, elementData = EMPTY_ELEMENTDATA. Expand to 1 the first time you add elements.

If no parameter is specified, elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; The first time you add an element, expand it to the default capacity of 10.

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);
    }
}

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if((size = elementData.length) ! = 0) { // c.toArray might (incorrectly) notreturn 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 main method

The add method adds elements

public boolean add(E e) { ensureCapacityInternal(size + 1); ModCount++ elementData[size++] = e; modCount++ elementData[size++] = e; // If the size of the array is large enough, assign the value to the position size, size plus 1return true;
}
Copy the code

private void ensureCapacityInternal(int minCapacity) {
    if(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 10 minCapacity = math. Max (DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { modCount++; // Overflow-conscious codeif(minCapacity -elementdata.length > 0) // If the required minimum capacity is greater than the current array size, expand grow(minCapacity); }Copy the code

private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); // The new capacity is the old capacity + the old capacity /2if(newCapacity -mincapacity < 0) // If the capacity increased by 1.5 times is smaller than the required minimum capacity, the minimum capacity is used. For example, when new ArrayList(0) is used, the old capacity is 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 Arrays using the copyOf method of the Arrays class}Copy the code

The set method sets the index index and returns the old element value at that index

public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element;return oldValue;
}
Copy the code

The get method gets the element

public E get(int index) { rangeCheck(index); // check the subscript firstreturnelementData(index); Private void rangeCheck(int 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

The remove method
- Remove (int index)
Arraycopy (Object SRC, int srcPos, Object dest, int destPos, int length) arrayCopy (Object SRC, int srcPos, Object dest, int destPos, int length) SRC source object, srcPos start subscript of the source object copy, Dest target object, destPos Start position of the source object copy to the target object, length Length of the copy

public E remove(int index) { rangeCheck(index); // first check the subscript range modCount++; E oldValue = elementData(index); int numMoved = size - index - 1; // Count the number of elements that need to be moved.if(numMoved > 0) Arraycopy (elementData, index+1, elementData, index, numMoved); // elementData[--size] = null; // Assign the last bit to null to facilitate garbage collectionreturn oldValue;
    }
Copy the code

- Remove (Object o) (remove the first matching element)

Nulls are considered separately for element deletion because null’s equals results always return false

    public boolean remove(Object o) {
        if(o == null) {// If null elements are deleted, use == to determine equalityfor (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true; }}else {
            for (int index = 0; index < size; index++)
                if(o.cube (elementData[index])) {// Delete elements that are not null using equals fastRemove(index);return true; // remove the first matching element and push out the loop, no longer looking}}return false; } // the fastRemove(int index) method is similar to the remove(int index) method, Private void fastRemove(int index) {modCount++; 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
    }
Copy the code

Size method to get the number of elements

public int size() {
    return size;
}
Copy the code

The isEmpty method directly determines whether the value of size is 0

public boolean isEmpty() {
    return size == 0;
}
Copy the code

The clear method clears the array of elements

public void clear() {
    modCount++;

    for(int i = 0; i < size; i++) elementData[i] = null; // Set all elements in the array to null to facilitate garbage collection. }Copy the code

IndexOf method, which returns the indexOf the first matched element, or -1 if there is no match

public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return- 1; }Copy the code

The lastIndexOf method returns the indexOf the last matched element, similar to indexOf, but looking backwards as it traverses the array

public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return- 1; }Copy the code

Array.copyof (T[] Original, int newLength); the two-parameter copyOf the Arrays method calls its own three-parameter copyOf. The third argument defaults to the type of the source array. The array type in ArrayList is Object[], so the returned array type is Object[].

ArrayList =new ArrayList<>(); String[] array= (String[]) list.toarray (); Throws an Exception in the thread “is the main” Java. Lang. ClassCastException: [ljava.lang.Object; cannot be cast to [ljava.lang.String;

public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}
Copy the code

Array.copyof (T[] original, int newLength) method

public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}
Copy the code

Arrays.copyOf(T[] original, int newLength, Class<? Extends Object[]> newType) method

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}
Copy the code

ArrayList also has a toArray method that requires passing in an array parameter to avoid the class conversion exception above.

public <T> T[] toArray(T[] a) {
    if (a.length < size)
        // Make a new array of a's runtime type, but my contents: return (T[]) Arrays.copyOf(elementData, size, a.getClass()); System.arraycopy(elementData, 0, a, 0, size); if (a.length > size) a[size] = null; return a; }Copy the code

Sort method (new in JDK1.8) to sort the elements of the list using the arrays.sort method

public void sort(Comparator<? super E> c) {
    final int expectedModCount = modCount;
    Arrays.sort((E[]) elementData, 0, size, c);
    if(modCount ! = expectedModCount) { throw new ConcurrentModificationException(); } modCount++; }Copy the code

SubList

SubList method to get the subList

public List<E> subList(int fromIndex, int toIndex) { subListRangeCheck(fromIndex, toIndex, size); // subscript range checkreturnnew SubList(this, 0, fromIndex, toIndex); } static void subListRangeCheck(int fromIndex, int toIndex, int size) {if (fromIndex < 0)
        throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
    if (toIndex > size)
        throw new IndexOutOfBoundsException("toIndex = " + toIndex);
    if (fromIndex > toIndex)
        throw new IllegalArgumentException("fromIndex(" + fromIndex +
                                           ") > toIndex(" + toIndex + ")");
}
Copy the code

SubList is an inner class of ArrayList. SubList does not store an array of elements. Instead, SubList uses member variables to record subscripts in the parent list. SubList also has methods like add, set, get, size, and so on. The method body is basically the same as the method in ArrayList or it calls the method in ArrayList.

private class SubList extends AbstractList<E> implements RandomAccess { private final AbstractList<E> parent; Private final int parentOffset; Private final int offset; // Offset int size; SubList(AbstractList<E> parent, int offset, int fromIndex, int toIndex) {this.parent = parent; this.parentOffset = fromIndex; this.offset = offset + fromIndex; this.size = toIndex - fromIndex; this.modCount = ArrayList.this.modCount; } the add,setGet methods, etc... }Copy the code

The Iterator Iterator

Iterator is a standard access method for iterating through collection classes. It abstracts the access logic from the different types of collection classes without exposing the internal structure of the collection to the client. For example, if we use a for loop to traverse a list, ArrayList and LinkedList require two different methods to access the elements, and if ArrayList is replaced with LinkedList in the future code, we will need to modify the heavily used code.

We first use the list iterator() method to get the list iterator. We then use the hasNext method of the iterator to determine if there are any more elements. Next returns an element and remove removes the returned elements.

public Iterator<E> iterator() {
    returnnew Itr(); } private class Itr implements Iterator<E> { int cursor; // The next element returns the subscript int lastRet = -1; ExpectedModCount = expectedModCount () {expectedModCount = expectedModCount; // Expected number of changes, used for fail-fast public BooleanhasNext() {
        returncursor ! = size; } @SuppressWarnings("unchecked")
    public E next() { checkForComodification(); / / fail - fast mechanism to check, if there are other threads to modify the list, will throw ConcurrentModificationException int I = cursor;if(I >= size) // throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData;if(I > = elementData. Length) / / check if the subscript bounds again throw new ConcurrentModificationException (); cursor = i + 1;return(E) elementData[lastRet = i]; // return the element and record lastRet} public voidremove() {
        if(lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.remove(lastRet); cursor = lastRet; lastRet = -1; // after the remove method is executed, it clears the record of the last returned element and cannot be called again. 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(); } final voidcheckForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}
Copy the code

JAVA collection: ArrayList source code analysis

ArrayList

Inheritance structure

Member variables

The constructor

The main method

SubList

The Iterator Iterator

Related Posts

Walk you through the raspberry PI transplant of LiteOS

Rust Language Case Study: The community makes Rust an easy choice for NPM

HTTPS describes the encryption process