Analysis of the internal principle of ArrayList

notes ： Analyzed in this article ArrayList The source code is based on Java 1.8 .

Header

I said before HashMap After the principle of , Let's have a look today ArrayList .

ArrayList It is also a very common collection class . It is ordered and can store repeated elements . ArrayList The bottom layer is actually an array , And it will be dynamically expanded .

Source code analysis

Construction method

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        //  Create an array of initial capacity 
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

public ArrayList() {
    //  Empty array by default 
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        //  Copy the elements in the collection into the array 
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

Copy

The code in the constructor is relatively short , Everyone can understand it .

add()

    public boolean add(E e) {
        //  Ensure the capacity of the array , Ensure that this element can be added 
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //  Put this element into the array 
        elementData[size++] = e;
        return true;
    }

Copy

Found in add() In the method , The code is very short . It can be seen that the previous pre operations have been put into ensureCapacityInternal In the method , This method will ensure that the element has a position in the array to put .

So let's take a look at this method ：

    private void ensureCapacityInternal(int minCapacity) {
        //  If the array is empty , Then the array will be initialized 
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            // DEFAULT_CAPACITY  by  10 , So call parameterless default  ArrayList  If the constructor is initialized , The default array capacity is  10
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
    
        ensureExplicitCapacity(minCapacity);
    }

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

        //  Ensure the capacity of the array , If not enough , call  grow  Method expansion 
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

Copy

Looked at half a day , The expansion is in grow Method , So we followed up .

    private void grow(int minCapacity) {
        //  The capacity of the current array 
        int oldCapacity = elementData.length;
        //  The new array is expanded to the original capacity  1.5  times 
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //  If the expansion capacity of the new array is still smaller than the minimum required capacity , Set the expansion capacity to the minimum required capacity 
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // Judge whether the capacity of the new array has exceeded the maximum array range ,MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        //  Copy elements to a new array 
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

Copy

The expansion method is actually to create a new array , Then copy the elements of the old array into the new array .

Of course ,add There's another way to overload add(int index, E element) , By the way, let's take a look at .

    public void add(int index, E element) {
        //  Judge  index  Is it beyond the scope of the index 
        rangeCheckForAdd(index);
        //  The operation is the same as before , Is to ensure that the capacity of the array is sufficient 
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //  Move the specified position and its subsequent data backward by one bit 
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        //  Add this element to the specified array location 
        elementData[index] = element;
        // ArrayList  Size change of 
        size++;
    }

Copy

Okay ,add The method is almost the same , There's one left addAll(Collection<? extends E> c) The method is to change the soup without changing the medicine , You can go back and have a look , I won't talk about it here .

get()

get It's easy , Just return the element at the specified position in the array .

    public E get(int index) {
        //  Check  index  Is it beyond the scope of the index 
        rangeCheck(index);
        //  Returns the element at the specified location 
        return elementData(index);
    }

Copy

remove()

    public E remove(int index) {
        //  Check  index  Is it beyond the scope of the index 
        rangeCheck(index);

        modCount++;
        //  Save the data that needs to be deleted 
        E oldValue = elementData(index);
        //  Let's specify the data behind the deleted location , Move one bit forward 
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        //  convenient  gc  Free memory 
        elementData[--size] = null; // clear to let GC do its work
        //  Return old value 
        return oldValue;
    }

Copy

remove It is mainly to move the following elements forward , Then set the value of the last bit to null . Last , Return the deleted value .

Again ,remove There's another way to overload remove(Object o) .

    public boolean remove(Object o) {
        if (o == null) {
            //  If the value of an element is  null  Words , Remove the element ,fastRemove  And the above  remove(int index)  It's similar 
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            //  If the value of an element is equal to  o  Words , Remove the element 
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

Copy

clear()

clear The method is nothing more than traversing the array , Then set all values to null .

    public void clear() {
        modCount++;

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

        size = 0;
    }

Copy

Footer

thus ,ArrayList The main methods are finished .ArrayList Source code or relatively simple , Basically, you can see clearly .

Let's summarize ：

1. ArrayList The bottom layer is based on arrays , So in get High efficiency when , and add perhaps remove When , Low efficiency ;
2. Call the default ArrayList If there is no parameter construction method , The initial capacity of the array is 10 ;
3. ArrayList It will automatically expand , expansion , Will expand the capacity to the original 1.5 times ;
4. ArrayList Not thread safe ;

So that's it today , Later, I'll tell you about LinkedList .