ArrayList overview

Hello, everyone. Today, let's introduce ArrayList. When it comes to ArrayList, many people know that its bottom layer is implemented by array, and the thread is unsafe. When it comes to its characteristics, they will say that it is fast to find and slow to add and delete, because everyone recites the interview questions. Let's talk about its underlying source code today.

ArrayList is more accurately implemented by dynamic arrays. The use of dynamic words here is to fully reflect its characteristics.

Moreover, ArrayList is not thread safe, so it is more efficient, but is this absolute? The answer is No.

ArrayList underlying source code

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

private static final long serialVersionUID = 8683452581122892189L;

private static final int DEFAULT_CAPACITY = 10;

private static final Object[] EMPTY_ELEMENTDATA = {};

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

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

private int size;

}

(1) ArrayList inherits the AbstractList abstract class and implements RandomAccess, Cloneable and Serializable interfaces. RandomAccess enables it to access quickly.

(2) Cloneable is actually a tag interface. Only after this interface is implemented, can the clone method in the Object be rewritten in the class, and then the clone method can be called through the class. If this interface is not implemented, a clonnotsupportedexception (cloning is not supported) exception will be thrown.

(3) Serializable is a serialization interface that supports serialization and deserialization.

(4) DEFAULT_ Capability is the size of the default initialization set of ArrayList.

(5) EMPTY_ELEMENTDATA is an empty array of objects used to share empty array instances of empty instances.

(6) DEFAULTCAPACITY_EMPTY_ELEMENTDATA is the object used when creating a collection using the default constructor

(7) elementData is an array object used to store the current data.

(8) size is the size of the collection.

(9) When the elements in the set exceed the specified length of the array, the array will be expanded. The expansion operation is the reason for the slow storage operation of ArrayList. Especially when the amount of data is large, each expansion will consume more and more time.

ArrayList construction method source code

ArrayList(int initialCapacity)

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

(1) The constructor is very simple. It directly judges the size of the value passed in. If it is greater than zero, it directly initializes an array object of this length and assigns it to elementData. If it is equal to zero, empty the empty array object_ elementData is assigned to elementData. Otherwise, an exception is thrown directly.

(2) This constructor is generally used when initializing a collection with a large amount of data.

ArrayList()

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

(1) Set DefaultAttribute_ EMPTY_ elementData null array object assigned to elementData

ArrayList(Collection c)

public ArrayList(Collection<? extends E> c) {

    elementData = c.toArray();

    if ((size = elementData.length) != 0) {
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

Two main things have been done here:
(1) First convert the set c into an array, and then assign it to the elementData array object.

(2) Then judge whether size and are equal and not equal to 0. If yes, assign the data and re assign it to the array object elementData. Otherwise, assign the empty array object to elementData directly.

Source code analysis of ArrayList method

add() method

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

(1) Execute the ensureCapacityInternal method to judge whether the original array object needs to be expanded.

(2) Add the e object to the elementData array object.

Next, let's take a look at the source code of the ensureCapacityInternal method.

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

In ensureCapacityInternal, we call the ensureExplicitCapacity method and the calculateCapacity method. Let's look at the calculateCapacity method.

private static int calculateCapacity(Object[] elementData, int minCapacity) {

    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

(1) The main task here is to calculate the capacity. First, judge whether the elementData array object has an initialization size. If not, take default_ The larger of capacity or minCapacity is the capacity. If it has been initialized, minCapacity is the capacity.

Next, let's take a look at the source code of ensureExplicitCapacity:

private void ensureExplicitCapacity(int minCapacity) {

    modCount++;

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

(1) Execute the auto increment of modCount. modCount is the number of times the current list structure has been modified.

(2) Judge if minCapacity is greater than elementdata Length, otherwise, exit this method directly to add elements.

Next, let's look at the source code of the grow method:

private void grow(int minCapacity) {

    int oldCapacity = elementData.length;

    int newCapacity = oldCapacity + (oldCapacity >> 1);

    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;

    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);

    elementData = Arrays.copyOf(elementData, newCapacity);
}

(1) Here, first get the length of the original data elementData and assign it to a variable oldCapacity, then expand the original length by 1.5 times and pay it to oldCapacity.

(2) Judge whether minCapacity is greater than newCapacity. If yes, assign minCapacity to newCapacity. Why? Because from the previous layer by layer analysis, minCapacity is the minimum length allowed after capacity expansion, that is, the minimum length of actually stored data. If the length after capacity expansion is smaller than minCapacity, you can only use minCapacity as the length of the container.

(3) Then judge whether the new container length newCapacity is greater than the maximum allowed container length MAX_ARRAY_SIZE, if true, set the expansion length to the maximum available length.

(4) Copy, expand, and build a new array.

Next, let's look at the source code of hugeCapacity called by the grow th method:

private static int hugeCapacity(int minCapacity) {

    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();

    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}

(1) Directly judge whether minCapacity is less than zero, throw an exception, and then compare whether the minimum length allowed by the container is greater than MAX_ARRAY_SIZE, if true, assign the maximum value of Integer to minCapacity as the maximum length of the container.

add(int index, E element) method

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

(1) There are three main things to do here. The first is to judge whether the subscript is out of bounds. If so, an IndexOutOfBoundsException exception will be thrown.

(2) Then judge whether capacity expansion is needed. This method is the same as the above. It has been said and will not be repeated.

(3) Finally, move the object after executing the array object index one bit back and add the element to the specified position.

Next, let's take a look at the source code of rangeCheckForAdd

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

(1) Directly judge the index > size or index < 0 condition, and directly throw the array subscript out of bounds exception.

addAll(Collection c) method

public boolean addAll(Collection<? extends E> c) {
    return addAll(this.size, c);
}

public boolean addAll(int index, Collection<? extends E> c) {

    rangeCheckForAdd(index);

    int cSize = c.size();

    if (cSize==0)
        return false;

    checkForComodification();

    parent.addAll(parentOffset + index, c);

    this.modCount = parent.modCount;

    this.size += cSize;
    return true;
}


private void checkForComodification() {
    if (ArrayList.this.modCount != this.modCount)
        throw new ConcurrentModificationException();
}

(1) addAll(Collection c) method directly calls addAll(this.size, c). The first thing in addAll(this.size, c) is to judge whether the subscript is out of bounds.

(2) Then judge whether the size of c is greater than 0. If it is equal to 0, return false.

(3) Check whether the number of modifications is equal. If not, a concurrent modificationexception (concurrent modification) exception will be thrown directly. That is, when we loop the list with the iterator and add / delete elements with the list method, this error will occur.

(4) Insert the element into the array, assign the modification times to modCount, and finally increase the size by one

(5) When performing the add operation, first judge whether the subscript is out of range and whether it needs to be expanded. If it needs to be expanded, copy the array and expand by half by default. If the expansion is not enough, use the target size as the capacity after expansion, and then set the corresponding subscript element value.

get() method

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

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

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

(1) This is very simple. First, judge whether the subscript is out of bounds, throw an exception when it is out of bounds, and finally return the element value at the specified index position.

set() method

public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

(1) First judge whether it is out of bounds, then take the value of the original index position as oldValue, set the new value element to the index position, and finally return the old value oldValue.

remove() method

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

(1) Judge whether it is out of bounds, and then increase the modification times modCount value by 1, and then obtain the old value of the original index position.

(2) Then calculate the number of elements after the index position, move the element after the index position forward one bit, and finally return the old value.

remove(Object o) method

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}


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
}

(1) This method of deleting objects is relatively simple. First, judge whether the o object is null. If it is null, traverse the elements in the collection. If there is a null value, delete. The method of deleting the specified object is fastRemove. The principle is to calculate the number of elements after the index position, and then move the elements after the index forward one bit, Finally, the last bit is assigned a null value.

(2) If the logic executed is the same when the o object is a non null object, why write it separately? It is very simple, because it needs to call the o.equals(elementData[index] method to judge. If it is null, it will not report a null pointer exception.

Iterator iterator

public Iterator<E> iterator() {
    return new Itr();
}

private class Itr implements Iterator<E> {
    int cursor; 
    int lastRet = -1;
    int expectedModCount = modCount;
    Itr() {}

    public boolean hasNext() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        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() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet)；
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
}

(1) There are several important attributes in the iterator. int cursor is the index of the next element to be returned, and int lastRet = -1 = is the index of the last element to be returned. The default is - 1, which is not the case.

(2) The hasnext method determines whether the next element exists by determining whether the following subscript is the size of the array.

(3) The next method obtains the next element. First, call the checkForComodification method to check whether the number of modifications is consistent, then define the subscript of the next element and judge the subscript. If the subscript is greater than the number of elements contained in the ArrayList, throw a NoSuchElementException (no such element exception), and then get the elementData data object in the ArrayList, Judge the subscript again. If the judgment is inconsistent this time, it means that the array has been modified. Finally, point cursor +1 to the subscript of the next element. Finally, define lastRet as the subscript of the returned element, and then return the value corresponding to the subscript.

(4) remove removes the current element. First, judge whether the subscript lastRet of the last element is less than 0. If it is true, the element does not exist, throw an exception, then call checkForComodification to judge whether the modification times are consistent, then call the remove method of ArrayList, and finally re update the values of cursor, lastRet and expectedModCount.

last

A good attitude and a persistent heart are very important. Many people with high salaries want to learn from the front end, but few can learn the last. They give up when they encounter difficulties. This kind of person is everywhere. It is because some things are difficult that his return is great. We judge the level of a front-end developer, that is, his ability to solve problems.

Share some simple front-end interview questions and learning routes for you, If you poke here, you can get it for free

Then return the value corresponding to the subscript.

(4) remove removes the current element. First, judge whether the subscript lastRet of the last element is less than 0. If it is true, the element does not exist, throw an exception, then call checkForComodification to judge whether the modification times are consistent, then call the remove method of ArrayList, and finally re update the values of cursor, lastRet and expectedModCount.

last

A good attitude and a persistent heart are very important. Many people with high salaries want to learn from the front end, but few can learn the last. They give up when they encounter difficulties. This kind of person is everywhere. It is because some things are difficult that his return is great. We judge the level of a front-end developer, that is, his ability to solve problems.

Share some simple front-end interview questions and learning routes for you, If you poke here, you can get it for free

[external chain picture transferring... (img-h9430LrE-1627103942294)]