List It can be said that it is one of the most used data structures , Understand its internal implementation principle , It's very important . This article mainly talks about interpreting from the perspective of source code Java in ArrayList Data structure of .

One 、 Interface inheritance relationship

ArrayList The inheritance relationship is as follows .AaaryList Mainly achieved List Interface , Also marked as serializable Serializable、 Replicable CloneAble、 Support random access RandomAccess.

Two 、 data structure

ArrayList At the bottom of this is an array , Use generics to determine the type of data stored in the array .
Java The length of the array in is usually fixed , however ArrayList The length of is indeed uncertain . Why? ？
because ArrayList The underlying array will expand as the data grows , The expansion of an array is to create a new array with large capacity , Then copy the data from the old array into the new array .
Because it's an array , So support random access , And orderly .

3、 ... and 、 establish ArrayList( Constructor parsing )

ArrayList There are three constructors , as follows , They are nonparametric structures , Constructors whose parameters are numbers and constructors whose parameters are sets .

ArrayList<Object> list1 = new ArrayList<>();
ArrayList<Object> list2 = new ArrayList<>(1);
ArrayList<Object> list3 = new ArrayList<>(list2);

3.1 No arguments structure

Parameterless construction is simple , to elementData The assignment is DEFAULTCAPACITY_EMPTY_ELEMENTDATA,

elementData Is an object number , Used to store actual data

Be careful elementData Use transient modification . Indicates that Java The default serialization mechanism , Attributes modified by this keyword will not be serialized . and ArrayList Class implements the java.io.Serializable Interface , That is to say Java The default serialization mechanism . however elementData It is definitely impossible not to serialize during network transmission , Look at the source code and you will find ArrayList I have implemented the methods of serialization and deserialization .

and DEFAULTCAPACITY_EMPTY_ELEMENTDATA It's a static final An empty array .

3.2 ArrayList(int initialCapacity)

ArrayList You can specify one int As a parameter , This parameter can specify the initialization capacity of the underlying array . The code is simple , If it is greater than 0, Initialize the array with this number , Is equal to zero , Assign an empty array to the array , Less than zero , Throw an exception .

3.3 ArrayList(Collection<? extends E> c)

The logic of this method is not complicated , Directly convert the collection object to Object Array , And then assigned to elementData attribute . Note that the comment above declares that it may throw NullPointerException, Looking at the source code, we will find that when we pass in the element is null When it's worth it , Will be in c.toArray() Throw out NPE.

Four 、 Add an element to the collection

4.1 Add to specified . Location add(int index, E element)

When adding elements , Will pass first ensureCapacityInternal Determine whether there is enough space for new elements , The required space is the current number of elements +1.

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

ensureCapacityInternal The method will first confirm whether the capacity is sufficient , If not enough , Then expand the capacity . Be careful ArrayList The timing and of capacity expansion HashMap There's a difference ,ArrayList Only the underlying array is full , You can't put down the objects to be saved before expanding ,HashMap The expansion of is related to the loading factor , By default , Not when the container is full .
The following method is , Specific expansion logic , First of all calculateCapacity Method , Computing capacity , If it is empty , Then return to the default capacity 10 Or the current required capacity .
ensureExplicitCapacity Method to calculate whether the capacity of the underlying array meets the required capacity , If not , You need to expand .
grow Is the way to achieve capacity expansion , The new array is the old array 1.5 back , Copy the data of the old array to the new array .

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

   private void ensureExplicitCapacity(int minCapacity) {
    
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

 private void grow(int minCapacity) {
    
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 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);
    }

2.2 Add to specified location add(int index, E element)

This order and add Methods compared , One more. index Range judgment , And array backward , Others and add In the same way .

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

2.3 Add all addAll(Collection<? extends E> c)

addAll Methods and add Methods compared , Because many elements are added at one time , therefore ensureCapacityInternal The parameters of are different , The assignment method uses System.arraycopy Assign a value .

    public boolean addAll(Collection<? extends E> c) {
    
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

5、 ... and 、 Remove elements

5.1 Delete the specified index element E remove(int index)

When deleting elements , Judge the legitimacy of the subscript first , Then get the data that needs to be deleted , Then the method of copying through the array , Move the element of the deletion position forward .

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

3.2 Delete the element of the specified value remove(Object o)

remove(Object o) You need to go through groups , First element found , Delete , and remove(int index) comparison , The latter does not need to traverse the array , Just judge whether the index meets the range , therefore , Usually ： The latter is more efficient

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
    }

6、 ... and 、 Get elements

The method and simplicity of getting elements , Judge the correctness of subscript , Then directly return the subscript sequence number corresponding to the array .

public E get(int index) {
    
        rangeCheck(index);

        return elementData(index);
    }

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

7、 ... and 、 Traversing elements iterator()

About the traversal of arrays , Is an iterator based on an inner class , What is iterator , It is suggested to refer to the iterator pattern of the design pattern .

public ListIterator<E> listIterator() {
    
        return new ListItr(0);
    }

8、 ... and 、 summary

1.ArrayList At the bottom is the array , No default value specified , The default is an empty , When adding data , Capacity for 10 Or the quantity required , When the array is full , When continuing to add elements , It will be expanded to the original 1.5 times .

2.ArrayList Saved a modCount attribute , The operation of modifying the set will make it self increment . The purpose is , If, during traversal modCount Be modified , An exception will be thrown .

3.ArrayList There is also an internal maintenance size attribute , It is used to record the actual number of elements in the array .

size,modCount,elementData These member variables , It's all destined ArrayList Thread unsafe .

4.ArrayList Realized Iterator Interface , This indicates traversal ArrayList Using normal for Cycle ratio use foreach faster .