ArrayList of novice source code

First, talk about something else ： Now I have just finished litchi , It's also very sweet ,8 Someone is playing the piano in the building , On and off , Building roads , The sound of machinery is very noisy . There are two gardenias in the water cup on the table , The fragrance is full of , gladdening the heart and refreshing the mind , Life is still beautiful .

Take notes today ArrayList The process of source code .

Have a look first ArrayList The inheritance structure of

ArrayList Source code or relatively simple . Here is ArrayList Several member variables in

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    
    // serialize id
    private static final long serialVersionUID = 8683452581122892189L;

     // default ArrayList The capacity of 
    private static final int DEFAULT_CAPACITY = 10;

    // An empty one Object Array 
    private static final Object[] EMPTY_ELEMENTDATA = {};

    // An empty one Object Array 
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    //ArrayList An array of elements 
    transient Object[] elementData; // non-private to simplify nested class access

    //ArrayList Of size（ Number of elements included ）
    private int size;

ArrayList There is another inherited from AbstrctList A member variable of

protected transient int modCount = 0;

modCount Used to indicate the present List Number of structural modifications . Structural modification refers to the change List Of size Modification of , such as List Add or delete operations . Or in other ways , Modifications that make ongoing iterations likely to produce incorrect results .
stay List In the iteration of , If modCount It was modified , The iterator will throw a
ConcurrentModificationException abnormal .

Use ArrayList It is usually used when ArrayList To instantiate a ArrayList

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

It is a simple assignment operation , Now elementData It's just an empty Object Array .

Instantiation ArrayList You can specify ArrayList The length 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);
        }
    }

If initialCapacity Greater than 0, Just create a new one with the size initialCapacity Of Object Array , then elementData Point to this array . If initialCapacity be equal to 0, Just put EMPTY_ELEMENTDATA Assign a value to elementData , Now elementData It's an empty array .

Instantiate a through a collection ArrayList

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

If Collection c The length of is not equal to 0, Just put c Convert it into an array and copy it to elementData in , Otherwise, I will EMPTY_ELEMENTDATA Assign a value to elementData , Now elementData It's an empty array .

ArrayList Of add(E e) Method , This should be the most commonly used method

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

When adding elements, first ensure the location of the added elements size,（size+1） No more than elementData The length of . if （size+1） It's bigger than elementData The length of , Just put elementData Increase the length to the original length 1.5 times .

private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

Internally by calling ensureExplicitCapacity Method realization

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

        //  If it goes beyond elementData The length of , Increase elementData The length of 
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //elementData The new length is elementData Of the original length 1.5 times 
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        //  Copy elementData The elements in , And grow elementData The length of 
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

elementData The increased length is elementData Of the original length 1.5 times .

Make sure that the location of the element to be added is elementData In the future , You can add elements to elementData At the same time size To increase 1.

 elementData[size++] = e;
 return true;

add(int index, E element) Method

public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1); 
        // hold index The back includes index All the elements in the position move backward by one position 
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

First check index The scope of 0 To size Between

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

Check whether it is necessary to add elementData The length of , And then put index The back includes index All the elements in the position move backward by one position , Then put the elements in index position , And put size Add one .

elementData[index] = element; size++;

ArrayList Of addAll Methods and add In the same way

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

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

        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount

        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);

        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

get(int index) Method

rangeCheck(index);
return elementData(index);

First check if it's out of bounds , If you don't cross the line , Take out index The element at position returns

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

set(int index, E element) Method

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

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

First of all index No boundaries , And then update index Elements in position , return index Old elements in position .

contains(Object o) Method

public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

Through internal indexOf Method realization

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

If you're looking for Object by null, Will traverse elementData If elementData Element in is null, Returns the first is null The location of . If Object Not for null, Just call Object Of equals Method to compare , Return to the first o.equals(elementData[i]) Of Location . If you don't find it, go back -1.

remove(int index) Method

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

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        // If the deleted element is not the last element , To put index All the following elements move forward one position 
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
         // The last element is set to null,size Minus one . 
        elementData[--size] = null; 

        return oldValue;
    }

If the deleted element is not the last element , To put index All the following elements move forward one position , And then the last element is set to null,size reduce 1, Return the deleted value .

remove(Object o) Method

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;

First find the first element equal to the element to be deleted index, then fastRemove(index) Methods to remove , Delete successful return true, Otherwise return to false.

 private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        // If the last element is not deleted , To put index The following elements move forward one position .
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        //size reduce 1, Set the last element to null
        elementData[--size] = null;
    }

clear() Method

public void clear() {
        modCount++;

        //  Set all elements to null
        for (int i = 0; i < size; i++)
            elementData[i] = null;
        //size Set as 0
        size = 0;
    }

ending ： Reference link
【1】http://blog.csdn.net/fighterandknight/article/details/61240861
【2】http://www.jianshu.com/p/2cd7be850540