Source code analysis of ArrayList

Preface

ArrayList It is a very common data storage class , In this article, we will learn about ArrayList The internal data structure of , Start with the constructor

structure

        ArrayList<Object> arrayList1 = new ArrayList<>();
        ArrayList<Object> arrayList2 = new ArrayList<>(10);
        ArrayList<Object> arrayList3 = new ArrayList<>(arrayList1);

Here is ArrayList Let's look down one by one at the three constructors of the source code

First, post the source code of the above parameter structure

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

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};


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

It can be seen from the empty parameter structure ArrayList Array is used to store data , Just because we didn't add data here, we used one length by 0 Array of

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

This is a single parameter construction , You need to pass in the container length , An array will be created according to this length to store the data , Of course, this length is not fixed , When the maximum capacity is reached, we will see .

    public ArrayList(Collection<? extends E> c) {
        Object[] a = c.toArray();
        // notes 1
        if ((size = a.length) != 0) {
            if (c.getClass() == ArrayList.class) {
                // notes 2
                elementData = a;
            } else {
                // notes 3
                elementData = Arrays.copyOf(a, size, Object[].class);
            }
        } else {
            // replace with empty array.
            elementData = EMPTY_ELEMENTDATA;
        }
    }

notes 1: take arrayList Of size The variable is set to the length of the passed array , After that, add data from this size++;

notes 2: If it's delivered ArrayList Just the one that will be delivered directly arrayList The array in is assigned to the current arrayList

notes 3: Yes, it will come in Collection Data in the array in copy To a new data and point this new data to the current ArrayList Medium elementData 

Let's take a look ArrayList Addition, deletion and modification of

  increase

    public boolean add(E e) {
        // This variable is mainly used to add or delete in iterators 
        // Making it not throw exceptions is not the focus we need to grasp this time, which can be ignored for the time being 
        modCount++;
        add(e, elementData, size);
        return true;
    }


    // Really add 
    private void add(E e, Object[] elementData, int s) {
        // When s == elementData.length It means that the current data storage is full and needs to be expanded 
        if (s == elementData.length)
            elementData = grow();
        // Add data to the last digit 
        elementData[s] = e;
        // After storing data , Maintenance of size+1
        size = s + 1;
    }


    // Capacity expansion 
    private Object[] grow() {
        return grow(size + 1);
    }

    // The concrete implementation of expansion 
    private Object[] grow(int minCapacity) {
        int oldCapacity = elementData.length;
        // notes 1
        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            // notes 2
            int newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity, /* minimum growth */
                    oldCapacity >> 1           /* preferred growth */);
            // notes 3
            return elementData = Arrays.copyOf(elementData, newCapacity);
        } else {
            // notes 4
            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
        }
    }

Let's focus on what the expansion function does

notes 1: Judge whether it is currently constructed with null parameters ArrayList And the data has not been added. If yes, it will be executed back to the comment 4 

  notes 2: Here is to calculate the length to be expanded , This expansion rule is to expand the capacity at least 1, Usually, the capacity is expanded to the previous capacity 1.5 times

notes 3: Here is the data in the previous array copy In the new array and points to the new array

notes 4: This line of code will arrayList Expand the array in to 10 The length of

Adding data at a specified location is also a common method , Go straight to source

    public void add(int index, E element) {
        // Check whether the position to be inserted is legal 
        // If at present size = 10, The location of the data to be inserted is 11 At this time, it is illegal to throw an exception 
        rangeCheckForAdd(index);
        modCount++;
        final int s;
        Object[] elementData;
        // Determine whether capacity expansion is needed 
        // Join in ArrayList Of Size = 10,  In this function index Also equal to  10  At this time, we need to expand the capacity 
        if ((s = size) == (elementData = this.elementData).length)
            elementData = grow();
        // notes 1
        System.arraycopy(elementData, index,
                         elementData, index + 1,
                         s - index);
        // Add data to the specified location 
        elementData[index] = element;
        size = s + 1;
    }

Let's focus on the notes 1

Insert data at specified location , The witty little friend will think whether the data of the original location has been covered , Seeing this line of code, I believe you have a clear idea

Here we will start with the incoming subscript ,size Move back a position after finishing the data to make index The position is empty for new data to be inserted .

Delete

    public boolean remove(Object o) {
        final Object[] es = elementData;
        final int size = this.size;
        int i = 0;
        found: {
            if (o == null) {
                for (; i < size; i++)
                    if (es[i] == null)
                        break found;
            } else {
                for (; i < size; i++)
                    if (o.equals(es[i]))
                        break found;
            }
            return false;
        }
        fastRemove(es, i);
        return true;
    }


    public E remove(int index) {
        Objects.checkIndex(index, size);
        final Object[] es = elementData;

        @SuppressWarnings("unchecked") E oldValue = (E) es[index];
        fastRemove(es, index);

        return oldValue;
    }

There are two ways to delete , Method 1 Delete for the specified object , Compare whether the objects are equal by traversal. If they are equal, set the data of this position null Operate and move the subsequent data one bit forward , And set the last data to null And size -1 

The second method is to directly set the corresponding position to null, And move the subsequent data forward one bit , And set the last data to null And size -1 

modify

    public E set(int index, E element) {
        Objects.checkIndex(index, size);
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

It is simpler to modify. Set the element at the specified position as a new element without moving other elements

Inquire about

  public E get(int index) {
        Objects.checkIndex(index, size);
        return elementData(index);
    }

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

The query operation is to judge whether the subscript of the data to be retrieved is legal , If it goes beyond size -1 Throw out

outOfBoundsCheckIndex, If it is legal, take out the data directly through subscript 

summary

In the source code, we see ArrayList Add, delete, and modify the operations done in the query , We will find that intermediate insertion or deletion of data will trigger the operation of data displacement , Adding a lot of data will make ArrayList Frequent capacity expansion operations will have an impact on performance , Therefore, we should try to avoid using ArrayList